백준 2178_미로

미로(백준 2178)

https://www.acmicpc.net/problem/2178

처음 문제를 보았을 때,
BFS를 적용하는 것까지는 알았으나….
문제는 ‘최단 거리’를 어떻게
구할지 감이 안잡혔다

30분 정도 고민하다
다른 정답자 분의 아이디어를
체크하여 풀었다

Code

import sys

import queue

boardY,boardX = map(int,sys.stdin.readline().split())
board = []

for i in range(boardY):
    board.append(list(map(int,sys.stdin.readline().rstrip())))

def bfs(bX,bY):
    que = queue.Queue()
    que.put([0,0])

    dx = [1,0,-1,0]
    dy = [0,1,0,-1]

    while not que.empty():
        posY,posX = que.get()
        
        for i in range(4):
            nx = posX + dx[i]
            ny = posY + dy[i]

            if 0 <= nx <boardX and 0 <= ny < boardY and board[ny][nx] == 1:
                board[ny][nx] = board[posY][posX] + 1
                que.put([ny,nx])
        
    return board[bY-1][bX-1]

print(bfs(boardX,boardY))

해결 아이디어

1. 특정 지점을 방문할 때,
   해당 지점에서의 ‘방문수’를
   이전 지점 ‘방문수’ + 1의 값으로 만듦
2. 다만 방문하려는 지점의 방문 수가
   ‘1’이 아니라면 누군가 이미 방문했다는
   의미이므로, 해당 노드는 탐색하지 않음
   (개인적으로 이 부분이 헷갈렸는데
   BFS로 상하좌우를 모두 동시에 탐색하기에
   어느 다른 노드가 미리 더 ‘깊이’ 탐색하여
   돌아오는 경우를 막는다)
3. 최종 지점의 ‘방문수’를 반환