[python] BOJ 2178 미로 탐색

백준 2178 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

문제

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

 

풀이

출발 정점인 0,0 에서 도착 정점인 N-1,M-1 까지 가는 최단거리를 구해야한다.

bfs를 통해 그래프를 탐색하는데, 이때 도착정점까지 가는 동안 모든 정점에 대해 최단거리를 갱신해주면 도착정점까지의 최단거리를 구할 수 있게 된다.

 

1. 먼저 큐를 만들고 시작 정점인 0,0 을  큐에 넣는다.

2. 큐에 있는 정점을 꺼내서, 그 정점의 인접 정점 중 방문할 수 있는 정점을 찾는다.

3. 방문할 수 있는 정점을 큐에 넣고,  최단거리를 갱신한다.

4. 2~3 번 과정을 큐가 빌때까지 반복한다.

 

위의 과정을 반복하게 되면 bfs 를 통해 정점을 탐색하는 과정동안 각 정점에 대한 최단거리가 갱신된다.

 

코드는 아래와 같다.

from collections import deque """ 미로에서 bfs 알고리즘 1. 큐 생성 2. 큐에 첫번째 출발지 append 3. 큐가 빌때까지 while문 반복  3.1 큐에서 x,y 꺼내서  3.2 각 방향벡터에 대한 nx, ny 생성 후  3.3 가중치 업데이트 4. return graph[N-1][M-1] 마지막 정점의 거리 리턴 """ def bfs(x,y):     queue = deque()     queue.append((x,y))     while queue:         x,y = queue.popleft()         for i in range(4):             nx = x + dx[i]             ny = y + dy[i]                          # case 1             if nx < 0 or nx >= N or ny < 0 or ny >= M:                 continue             # case 2                     if graph[nx][ny] == 0:                 continue             if graph[nx][ny] == 1:                 graph[nx][ny] = graph[x][y] + 1                 queue.append((nx,ny))     return graph[N-1][M-1]                      dx = [ -1 , 1 , 0 , 0] dy = [ 0 , 0 , -1 , 1] N, M = map(int ,input().split()) graph = [] for i in range(N):     graph.append(list(map(int,input()))) print(bfs(0,0))

 

기억해야할 것

인접 정점은 nx, ny를 통해 나타내고

현재 방문하고 있는 정점은 x, y를 통해 나타낸다.