[프로그래머스] 블록 이동하기

https://programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

 

BFS 알고리즘으로 일어날 수 있는 조건을 주어 구현하였다. 각 조건마다 코딩하여서 조금 길다.

한 칸 이동이 예를 들면 가로로 긴 블록일 때 좌우로 한 칸의 움직임만 허용되는 건 줄 알았는데 문제를 자세히 읽어보니 위아래로 가능하여서 틀리는 이유를 찾는데 조금 애먹었던 문제였다.

 

from collections import defaultdict, deque

def solution(board):
    answer = 0
    N = len(board)
    queue = deque([(0, 0, 0, 1)])
    dic = defaultdict(int)
    
    for i in board:
        print(i)
    
    while queue:
        a, b, c, d = queue.popleft()
        value = dic[(a, b, c, d)] + 1 
        
        if a == c:
            if b - 1 >= 0 and board[a][b - 1] != 1 and dic[(a, b - 1, a, b)] == 0:
                dic[(a, b - 1, a, b)] = value
                queue.append((a, b - 1, a, b))

            if d + 1 < N and board[c][d + 1] != 1 and dic[(c, d, c, d + 1)] == 0:
                dic[(c, d, c, d + 1)] = value
                queue.append((c, d, c, d + 1))
            
            if a + 1 < N and board[a + 1][b] != 1 and board[a + 1][d] != 1:
                if dic[(a, b, a + 1, b)] == 0:
                    dic[(a, b, a + 1, b)] = value
                    queue.append((a, b, a + 1, b))

                if dic[(c, d, c + 1, d)] == 0:
                    dic[(c, d, c + 1, d)] = value
                    queue.append((c, d, c + 1, d))
                    
                if dic[(a + 1, b, c + 1, d)] == 0:
                    dic[(a + 1, b, c + 1, d)] = value
                    queue.append((a + 1, b, c + 1, d))

            if a - 1 >= 0 and board[a - 1][b] != 1 and board[a - 1][d] != 1:
                if dic[(a - 1, b, a, b)] == 0:
                    dic[(a - 1, b, a, b)] = value
                    queue.append((a - 1, b, a, b))

                if dic[(c - 1, d, c, d)] == 0:
                    dic[(c - 1, d, c, d)] = value
                    queue.append((c - 1, d, c, d))
                    
                if dic[(a - 1, b, c - 1, d)] == 0:
                    dic[(a - 1, b, c - 1, d)] = value
                    queue.append((a - 1, b, c - 1, d))
        else:
            if c + 1 < N and board[c + 1][d] != 1 and dic[(c, d, c + 1, d)] == 0:
                dic[(c, d, c + 1, d)] = value
                queue.append((c, d, c + 1, d))

            if a - 1 >= 0 and board[a - 1][b] != 1 and dic[(a - 1, b, a, b)] == 0:
                dic[(a - 1, b, a, b)] = value
                queue.append((a - 1, b, a, b))

            if b + 1 < N and board[a][b + 1] != 1 and board[c][b + 1] != 1:
                if dic[(a, b, a, b + 1)] == 0:
                    dic[(a, b, a, b + 1)] = value
                    queue.append((a, b, a, b + 1))

                if dic[(c, d, c, d + 1)] == 0:
                    dic[(c, d, c, d + 1)] = value
                    queue.append((c, d, c, d + 1))
                    
                if dic[(a, b + 1, c, d + 1)] == 0:
                    dic[(a, b + 1, c, d + 1)] = value
                    queue.append((a, b + 1, c, d + 1))

            if b - 1 >= 0 and board[a][b - 1] != 1 and board[c][b - 1] != 1:
                if dic[(a, b - 1, a, b)] == 0:
                    dic[(a, b - 1, a, b)] = value
                    queue.append((a, b - 1, a, b))

                if dic[(c, d - 1, c, d)] == 0:
                    dic[(c, d - 1, c, d)] = value
                    queue.append((c, d - 1, c, d))
                
                if dic[(a, b - 1, c, d - 1)] == 0:
                    dic[(a, b - 1, c, d - 1)] = value
                    queue.append((a, b - 1, c, d - 1))
    
    if dic[(N - 1, N - 2, N - 1, N - 1)] == 0 or dic[(N - 2, N - 1, N - 1, N - 1)] == 0:
        answer = max(dic[(N - 1, N - 2, N - 1, N - 1)], dic[(N - 2, N - 1, N - 1, N - 1)])
    else:
        answer = min(dic[(N - 1, N - 2, N - 1, N - 1)], dic[(N - 2, N - 1, N - 1, N - 1)])
    
    return answer

print(solution([[0, 0, 0, 1, 1], [0, 0, 0, 1, 0], [0, 1, 0, 1, 1], [1, 1, 0, 0, 1], [0, 0, 0, 0, 0]])) # 7