[BFS] 미로에서 길찾기 게임

 

BFS 사용하기

가장 가까운 칸들부터 탐색하며 갈 수 있는지 판단하기 때문에 현재 있는 위치의 동서남북을 탐색한다면 괴물이 있는 곳은 피할 수 있을 거 같다.

큐를 사용하여 주변을 탐색을 하는데 (N,M)까지 가야하므로 오/아/왼/위 순으로 탐색을 진행하면서 큐에 넣어야 겠다.

 

최소 거리 이동한 칸의 개수를 어떻게 측정?

큐에 넣을 때, bfs를 위한 좌표값만 큐에 넣는 것 이 아닌 거기까지 걸린 비용도 같이 리스트로 묶어서 넣어버리면 어떠할까 라는 아이디어

예를 들어 첫 좌표에서 동서남북을 탐색해서 큐에 넣는 주변 노드들은 모두 2랑 묶어서 큐에 넣는 방식

큐에 넣다가 만약에 N,M을 만난 경우 그 때 cnt 수를 return 하는 방식

가장 먼저 N,M에 도착했다는 것은 가장 짧은 거리로 왔다는 것과 같기 때문!

Visited

굳이 따로 방문을 체크하는 리스트를 만들 필요 없이 graph 자리에서 1을 0으로 바꾼다

정리

• 각 좌표에서 오/아/왼/위 순으로 훑어보며 좌표와 Cnt 값을 묶어서 큐에 저장
• 훑어볼 때, 만약 N, M을 초과하는 좌표가 나온다면 버린다
• 훑어볼 때, 만약 graph가 0이라면 visted이거나 괴물이 있으므로 버린다
• N,M에 도착하게 된다면 Cnt값을 Return한다

from collections import deque

N, M = map(int, input().split())

graph = []
for i in range(N):
    graph.append(list(map(int, input())))

# Visited는 따로 생성하지 않고 방문시, 1->0으로 변경

direct_row = [0, 1, 0, -1]
direct_col = [1, 0, -1, 0]

def bfs(row, col):
    q = deque()
    cnt = 1
    q.append([row, col, cnt])
    while len(q) != 0 :
        nxt = q.popleft()
        for d in range(4):
            new_node = [nxt[0] + direct_row[d], nxt[1] + direct_col[d], nxt[2] + 1]
            if new_node[0]<0 or new_node[0]>=N or new_node[1]<0 or new_node[1]>=M:
                continue
            if graph[new_node[0]][new_node[1]] == 1:
                if new_node[0] == N-1 and new_node[1] == M-1:
                    return new_node[2]
                else:
                    graph[new_node[0]][new_node[1]] = 0
                    q.append(new_node)


print(bfs(0,0))