백준[2178] - 미로탐색

 

 

문제

2178번: 미로 탐색

 

 

 

작성한 코드

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(N)]

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

def bfs(x, y):
    q = deque()
    q.append((x, y))

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue

            if graph[nx][ny] == 1:
                q.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1
                
    return graph[N-1][M-1]

print(bfs(0, 0))

- 최단 거리를 구하는 문제이기 떄문에 BFS를 활용하여 문제를 풀어보았다. (deque() 사용)

 

- N과 M을 입력받고, 그래프 내용을 입력받기 위해서 리스트 graph를 미리 선언해준다.

- 시작점과 끝점이 정해져있지만 NxM 전체를 탐색하면서 비교해야 하기 때문에 dx, dy를 선언해준다. (상하좌우)

- bfs(x, y) 함수를 선언하고, 해당 함수에 시작점인 (0,0)을 넣은 뒤, 해당 함수의 return 값을 최종적으로 print() 해준다.

 

- BFS 이기 때문에 deque()인 q를 선언하고, 해당 큐에 (x,y)를 append()로 추가해준다.

- q가 빌 때까지 while문을 반복한다.

- q에서 popleft()한 값을 x, y에 각각 저장한다.

- for문을 돌면서 상하좌우 4가지 방향을 확인하고, 새로운 좌표는 nx, ny에 저장한다.

- 만약 nx, ny 모두 NxM 범위를 넘어가면 continue로 건너뛴다.

- 범위 내일 경우, graph[nx][ny]의 값이 1인 경우 → q에 추가해주고, 이전 좌표에 해당하는 값에 +1을 하여 저장한다.

- 최종적으로 graph[N-1][M-1]에 최단거리 값이 들어가게 된다. (인덱스가 0부터 시작해서 N, M 각각 1씩 빼줘야한다.)