백준 2178번 - 미로 탐색

문제 출처 : https://www.acmicpc.net/problem/2178

코드

from collections import deque
COL, ROW = map(int, input().split())

MAP = []
for _ in range(COL):
    MAP.append(list(map(int, input())))
               
visited = [[False] * ROW for _ in range(COL)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
          
def bfs(MAP, s_col, s_row):
    q = deque()
    q.append((s_col, s_row, 0))
    visited[s_col][s_row] = True
    
    while q:
        x, y, dist = q.popleft()
        if x == COL-1 and y == ROW-1:
            return dist+1
            
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]   
               
            if nx < 0 or ny < 0 or nx >= COL or ny >= ROW:
                continue
               
                
            if visited[nx][ny] == False and MAP[nx][ny] == 1:
                q.append((nx, ny, dist+1))
                visited[nx][ny] = True
        
               
print(bfs(MAP, 0, 0))

풀이

어쩌면 bfs의 기초라고 할 수 있는 아주 간단한 문제이다. (는 무슨 오랜만에 했더니 땀 흘리면서 풀었다,, 부들부들,,) bfs유형을 푼다 하면 보통 이러한 틀에서 문제가 출제되기 때문에, 구조를 잘 알아두면 아주 도움이 될 것 같다.