[백준] 2178번 미로탐색 - 파이썬(Python)

문제 (링크)

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

2178번: 미로 탐색

 

나의 풀이

from collections import deque

n, m = map(int, input().split())
graph = []
# 상 하 좌 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(n):
    graph.append(list(map(int, input())))

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]
        
            if nx < 0 or nx >= n or ny <0 or ny >= m:
                continue
        
            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]

print(bfs(0, 0))

 

bfs 방식으로 그래프를 순회하며 최단거리를 구하는 문제이다.

 

queue에 시작부터 움직이는 동안의 위치를 담아주고 하나씩 pop하며 해당 위치와 인접한 위치 중 움직일 수 있는 위치(graph[x][y] == 1)로만 움직여주고, 움직인 후에는 해당 그래프의 값에 1씩 더해 이동거리를 기록해준다.

 

 

유튜브 강의 나동빈님의 이.코.테 DFS / BFS 알고리즘 강의를 들은 후, 강의에서 제공하는 문제와 동일한 형태의 문제를 발견해 처음부터 끝까지 코드를 직접 작성해보았다.

 

아직은 2차원 배열에서 이동을 한다는 것이 익숙치 않은 개념이긴 하지만 하다보면 좋아질거라 믿는다.