[이코테] 미로 탈출 (BFS) / [BOJ] 2178. 미로 탈출

1. 해결 방법

"""
1. 아이디어
- 2차원 배열을 사용
- BFS를 돌면서 한번 움직일 때마다 +1, 입구에서 출구까지의 거리를 계산 후 최소 이동 거리를 갱신
- 출잘점 (1, 1)에서 목적지 (n, m)까지 이동하는데 해당 노드에 처음 도달한 경우(1일 때) 모든 방향의 노드 값을 +1 해준다.

2. 시간복잡도
- O(V + E)
- V : m X n = 200 X 200 = 40000
- E : 4V = 4 * 40000

3. 자료구조
- 이차원 배열 : int[][]
- 방문 기록 : bool[][]
- BFS(Queue)
"""

노드를 이동할 때마다 노드의 값에 +1을 해주면 된다. 단, 상하좌우를 판단해서 이동할 수 있는 경로가 다수일 경우에는 모든 방향에 +1 처리를 해준다. 
그러면 결국 우측 하단(n-1, m-1) 탈출 노드에서는 최단 거리의 노드 값을 도출해낼 수 있다.

 

 

2. 정답 코드

입력 예제

5 6
101010
111111
000001
111111
111111

출력 예제

10

 

 

코드

from collections import deque

n, m = map(int, input().split())
map = [list(map(int, input())) for _ in range(n)]
# chk = [[False] * m for _ in range(n)]


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


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

    while q:
        ey, ex = q.popleft()
        for k in range(4):
            ny = ey + dy[k]
            nx = ex + dx[k]
            if 0 <= nx < m and 0 <= ny < n:
                if map[ny][nx] == 1:
                    map[ny][nx] = map[ey][ex] + 1
                    q.append((ny, nx))

    return map[n-1][m-1]

# main
print(bfs(0, 0))

 

위치를 옮겨갈때 자리마다 숫자 값을 올려주는 아이디어!