[DFS/BFS] 블록 이동하기

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 20 + a

1. 문제 설명

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

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

2. 접근 방식

- BFS를 활용해서 목표 지점까지 최단경로를 구하는 문제로 이해할 수 있다.  

- 이동하는 경우와 회전하는 경우를 다 계산해서 로봇이 특정 위치에서 움직일 수 있는 모든 가능한 경우를 리턴해주는 부분을 만든다.

- 그리고 해당 리스트를 활용해서 최단경로를 계산한다. 

3. 코드

from collections import deque

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]
    
    # [상, 하, 좌, 우]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # 모든 방향 확인
    for i in range(4):
        pos1_next_x, pos1_next_y, pos2_next_x, pos2_next_y = pos1_x+dx[i], pos1_y+dy[i], pos2_x+dx[i], pos2_y+dy[i]
        if board[pos1_next_x][pos1_next_y] == 0 and board[pos2_next_x][pos2_next_y] == 0:
            next_pos.append({(pos1_next_x, pos1_next_y), (pos2_next_x, pos2_next_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

4. 코멘트

- 오랜만에 처음부터 끝까지 어떻게 구현하지 라는 생각이 좀 많이 들었던 문제였다. 그리고 해답을 보고서도 이해하는데 시간이 꽤나 걸렸었다. 

- 결국 주요 골자는 BFS에 최단경로라는 요소가 들어간 문제였다. 하지만 그러기 위해서 고려해야 하는 조건이나 다뤄야 하는 좌표가 많아서 많이 헷갈렸던 문제였다.