[DFS/BFS] 블록 이동하기

1. 문제

오른쪽 하단 끝으로 이동하기

 

2. 입력

# SET - 1
board = [[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]]

 

3. 출력

# SET - 1
result = 7

 

4. 풀이

DFS로 풀려고했는데 visited 처리를 제대로 못했다.

visited처리를 하면서 혼돈에 빠져서 결국 해결못하고 GG

 

DFS로 하면 모든 경로를 다 탐색하므로 오래걸리고 안될 수 밖에;;

판단을 잘못했다.

 

BFS로 풀면,

그 전에 방문한곳은 cost가 무조건 낮은걸로 채워져있을테니

결국 N, N에 도착하는 cost는 최저 코스트가 될 것이다.

 

그러므로, 다음 이동할 position을 미리 계산해서 리스트에 담은 뒤,

그것을 큐에 cost와 함께 넣어주면, 이미 가본 곳은 건너뛰고, N, N까지 최단거리로 갈 것이다.

 

그리고 지도를 한 칸 확장해서 외부를 벽으로 세우니 코드가 간결해진 것을 확인할 수 있었다.

 

그리고 회전할 때 판단을 한번에 하는 방법을 유심히 살펴보자.

로봇의 왼쪽위, 오른쪽위가 뚫려있다면 위로 회전이 가능한 것

반대도 마찬가지,

로봇의 오른쪽 위 오른쪽 아래가 뚫려있다면 오른쪽으로 회전이 가능한 것

반대도 마찬가지

 

알고리즘은 하면 할수록 어렵다...

5. 코드

from collections import deque

FOUR_DIR = [(-1,0), (0,1), (0,-1), (1,0)]
def get_next_pos(pos, board):
    next_pos = []
    pos = list(pos)
    pos1_x, pos1_y, pos2_x, pos2_y = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
    for dx, dy in FOUR_DIR:
        n1_x, n1_y, n2_x, n2_y = pos1_x+dx, pos1_y+dy, pos2_x+dx, pos2_y+dy
        if board[n1_x][n1_y] == 0 and board[n2_x][n2_y] == 0:
            next_pos.append({(n1_x, n1_y), (n2_x, n2_y)})
    if pos1_x == pos2_x:
        for i in [-1, 1]:
            if board[pos1_x+i][pos1_y] == 0 and board[pos2_x+i][pos2_y] == 0:
                next_pos.append({(pos1_x, pos1_y), (pos1_x+i, pos1_y)})
                next_pos.append({(pos2_x, pos2_y), (pos2_x+i, pos2_y)})
    elif pos1_y == pos2_y:
        for i in [-1, 1]:
            if board[pos1_x][pos1_y+i] == 0 and board[pos2_x][pos2_y+i] == 0:
                next_pos.append({(pos1_x, pos1_y), (pos1_x, pos1_y+i)})
                next_pos.append({(pos2_x, pos2_y), (pos2_x, pos2_y+i)})
    return next_pos

def solution(board):
    n = len(board)
    new_board = [[1]*(n+2) for _ in range(n+2)]
    for i in range(n):
        for j in range(n):
            new_board[i+1][j+1] = board[i][j]
            
    q = deque()
    visited=[]
    pos = {(1,1), (1,2)}
    q.append((pos, 0))
    visited.append(pos)
    while q:
        pos, cost = q.popleft()
        if (n, n) in pos:
            return cost
        for next_pos in get_next_pos(pos, new_board):
            if next_pos not in visited:
                q.append((next_pos, cost+1))
                visited.append(next_pos)

    return 0