백준 [python] 2178 미로탐색

전체코드

from collections import deque
if __name__ == "__main__":
    N,M = map(int,input().split())
    graph=[]
    for i in range(N):
        graph.append(list(map(int,input())))
    
    visited = [ [0 for _ in range(M)] for _ in range(N) ]
    visited[0][0] = 1
    queue = deque([[0,0]])
    dists = [[-1,0],[1,0],[0,1],[0,-1]]
    def bfs():
        while queue:
            [i,j] = queue.popleft()
            for dist in dists:
                nextI = i + dist[0]
                nextJ = j + dist[1]
                if nextI < 0 or nextJ < 0 or nextI >= N or nextJ >= M:
                    continue
                if graph[nextI][nextJ] == 0 or visited[nextI][nextJ] != 0:
                    continue
                visited[nextI][nextJ] = visited[i][j] + 1
                queue.append([nextI,nextJ])
    bfs()
   
    print(visited[N-1][M-1])

복기

0. deque를 선언할 때 미리 초기값을 넣어주려면 deque([초기값])을 하면 된다. 이번 문제에서 [0,0]값을 미리 넣어주고 싶어서 deque([[0,0]])을 해주었다.
1. 인접행렬로 그래프를 표현했다
2. visited 배열에 cnt를 세주었다. 이상하게 파이썬 0으로 만들어진 리스트를 다음처럼 선언했더니 동작이 안되었다. 그래서 for in range로 만들었다.

visited = [[0]*N]]*M
visited[0][0] = 1
// 의도한 값[[1,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
// 이상하게 동작[[1,0,0,0,0],[1,0,0,0,0],[1,0,0,0,0],[1,0,0,0,0],[1,0,0,0,0]]

3. 이런 그래프 문제에서 늘상있는 인덱스 문제를 (1,1)은 (0,0)로 (N,M)은 (N-1,M-1)처럼 i-1 , j-1씩 해주었다
4. dists 배열을 두어 for문을 돌면서 동서남북 방향으로 가도록 만들었다
5. 다음 예외 조건일 때는 queue에 해당 좌표를 넣으면 안된다
   5-1. 막힌경우 또는 방문한 경우에는 제외해야한는데 or연산자가 아닌 and연산자로 해서 헤매었다.

if nextI < 0 or nextJ < 0 or nextI >= N or nextJ >= M:
	continue // 좌표를 벗어난 경우
if graph[nextI][nextJ] == 0 or visited[nextI][nextJ] != 0:
	continue // 미로가 막힌경우 또는 방문한 경우

6. visited[nextI][nextJ] 배열에 이전에 visited[i][j] +1을 해준다

후기

오랜만에 bfs문제를 풀어보니 헷갈리는 부분이 많았다. 그래프 문제를 좀 더 집중해서 풀고 연습해야겠다