2178 미로탐색

1. 정답 코드

문제의 내 정답 코드는 다음과 같다.

from collections import deque

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

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

visited = [[False for _ in range(M)] for _ in range(N)]

dx = [0 , 0 , -1 , 1] # 상 하 좌 우
dy = [-1, 1 , 0 , 0] # 상 하 자 우

def BFS(graph,start,visited):
    q = deque()
    q.append(start)
    visited[start[0]][start[1]] = True

    while q :

        (x,y) = q.popleft()

        for j in range(4):
            nx = x + dx[j]
            ny = y + dy[j]
            if nx < 0 or nx >= N or ny < 0 or ny >= M :
                # 맵을 벗어나면 continue
                continue
            if graph[nx][ny] == 0 :
                # 벽에 가로막히면 continue
                continue
            if graph[nx][ny] == 1:
                # 방문했을 때 첫 방문이면
                # x,y의 방법보다 1만큼 더 간 것이기 때문에
                # 간단히 1을 더해주자.
                graph[nx][ny] = graph[x][y] + 1
                q.append((nx,ny))
    return graph[N-1][M-1]


print(BFS(graph,(0,0),visited))

2. 문제 풀이

미로 탐색과 같은 문제를 풀기 위해 중요한 포인트들이 있다.

1. 모든 경로를 “다” 가보고 원하는 목적지의 탐색 값을 출력하는 것
2. 현재 노드에서 탐색할 다른 노드를 찾기 위해 즉, 움직이기 위해선 먼저 dx,dy를 만들어 놓고 시작하면 편하다.
3. 각 노드마다 1의 값이 주어져있으니 따로 visited 리스트를 만들지 말고, graph의 노드 값이 1이면 방문하지 않았다고 생각하자.