[백준] 2178번: 미로 탐색 Python 풀이

[백준] 2178번: 미로 탐색 Python 풀이

문제

 

백준 2178번 미로 탐색 문제입니다.

(1,1)에서 (N, M)까지 최소 거리를 구하는 문제이므로 BFS를 이용해서 풀 수 있습니다.

---

BFS

타일형 문제는 BFS로 풀 경우, 각 타일마다 이동할 수 있는 방향을 모두 계산하여

다음 타일이 조건에 부합한다면 Queue에 저장합니다.

 

문제에서는 적혀있지 않지만 4방향으로만 움직일 수 있기 때문에 이동 방향을 정해줍니다.

moves = [[0,1], [0,-1], [1,0], [-1,0]]

 

시작 위치는 (1,1)로 고정되어 있으니 해당 값을 Queue에 넣습니다.

Python 리스트는 0부터 시작하므로 [0,0]을 넣어줍니다.

 

각 타일에서 갈 수 있는 다음 타일의 경우를 구한 뒤, 몇 가지 조건을 검사합니다.

1. 다음 타일의 위치가 미로를 벗어나지 않는지 0 <= Y < N , 0 <= X < M
2. 다음 타일을 방문한 적이 있는지 Visited[Y][X] = False
3. 다음 타일의 값이 1인지 Table[Y][X] = 1 

따라서 각 타일은 좌표, 값, 방문 여부, 탐색 횟수를 가지고 있어야 합니다.

각 타일마다 탐색을 수행하여 3가지 조건과 모두 일치하는 타일만 선택하여 Queue에 저장합니다.

이때, 탐색 횟수는 이전 타일에서의 탐색 횟수 + 1입니다.

 

[N-1, M-1]에 도달한 경우 해당 타일의 탐색 횟수를 출력하며 종료하면 문제 풀이가 끝납니다.

 

전체코드는 다음과 같습니다.

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().strip().split(" "))
table = []

# 미로 초기화
for _ in range(n) :
    table.append([ int(i) for i in input().strip() ])

# 방문 여부 초기화
visited = [ [ [False, 0] for _ in range(m) ] for _ in range(n) ] 
queue = deque()

# 초기 경로는 (0,0)이며 탐색 경로 +1
queue.append([0,0])
visited[0][0] = [True, 1]

# 이동 가능한 방향
moves = [[0,1], [0,-1], [1,0], [-1,0]]

# BFS
while queue :
    current = queue.popleft()
     
    # (N-1, M-1)에 도달한 경우 종료
    if current[0] == n - 1 and current[1] == m - 1 :
        print(visited[current[0]][current[1]][1])
        exit()
        
    # 4방향 탐색 
    for move in moves :
        next_y = current[0] + move[0]
        next_x = current[1] + move[1]
        
        # 다음 타일이 미로를 벗어나지 않고 방문한 적이 없을 경우
        if 0 <= next_y < n and 0 <= next_x < m and not visited[next_y][next_x][0] :                    
            # 다음 타일의 값이 1인 경우
            if table[next_y][next_x] != 0 :
                # Queue에 저장
                visited[next_y][next_x][1] += visited[current[0]][current[1]][1] + 1
                queue.append([next_y, next_x])
                
            visited[next_y][next_x][0] = True