2178번: 미로 탐색

2178번: 미로 탐색

 

BFS로 최단 거리를 탐색하는 문제.

처음에는 단순히 visited배열에 해당 칸 방문 여부만 저장했는데,

거기에 더해 방문하기까지 방문한 칸수를 저장하면 도착지까지의 최단 시간을 구할 수 있다.

---

풀이 코드

# 2178번: 미로 탐색
from collections import deque

n, m = map(int, input().split())
graph = []
visited = [[0] * m for _ in range(n)] # 현재 칸까지 방문한 칸 수를 저장(0일 경우 방문하지 않은 것)
for i in range(n):
    row = list(map(int, input()))
    graph.append(row)

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

def bfs(graph, x, y, visited):
    queue = deque([(x, y)]) # 시작위치를 큐에 넣고 시작
    visited[x][y] = 1

    while queue:
        x, y = queue.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] == 0:
                continue
            
            # 이동할 수 있는 칸이고, 방문하지 않은 경우
            if graph[nx][ny] == 1 and visited[nx][ny] == 0:
                queue.append((nx, ny))
                visited[nx][ny]  = visited[x][y] + 1
                if (nx, ny) == (n - 1, m - 1):
                    return visited[n-1][m-1]
                

print(bfs(graph, 0, 0, visited))

 

---

 

...
visited = [[0] * m for _ in range(n)] # 현재 칸까지 방문한 칸 수를 저장(0일 경우 방문하지 않은 것)
...


def bfs(graph, x, y, visited):
  ...
            
            # 이동할 수 있는 칸이고, 방문하지 않은 경우
            if graph[nx][ny] == 1 and visited[nx][ny] == 0:
                queue.append((nx, ny))
                visited[nx][ny]  = visited[x][y] + 1
                if (nx, ny) == (n - 1, m - 1):
                    return visited[n-1][m-1]

 

이 테크닉을 잘 기억해둬야겠다.