[백준 / 2178] 미로 탐색 - Python

'다익스트라(Dijkstra) 알고리즘'을 이욯하여 풀었으므로, 해당 알고리즘에 대한 선행이 필요하다.

 

2021.03.18 - [# Coding/# Algorithm] - [보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python

[보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python

<다익스트라 알고리즘>

import sys
import heapq


def dijkstra(graph, N, M):
    distances = [[float('inf') for _ in range(M)] for _ in range(N)]

    distances[0][0] = 1

    queue = [[1, [0, 0]]]

    # 상하좌우
    dn = [-1, 1, 0, 0]
    dm = [0, 0, -1, 1]

    while queue:
        current_distance, current = heapq.heappop(queue)
        current_n, current_m = current

        if current_distance > distances[current_n][current_m]:
            continue

        for i in range(4):
            n = current_n+dn[i]
            m = current_m+dm[i]
            if 0 <= n < N and 0 <= m < M and graph[n][m] == 1:
                new_distance = current_distance+1

                if new_distance < distances[n][m]:
                    distances[n][m] = new_distance

                    heapq.heappush(queue, [new_distance, [n, m]])

    return distances[N-1][M-1]

 

시간을 줄이기 위해 sys와 heqpq를 import 했다.

 

distances는 graph와 똑같은 크기의 거리를 담고 있는 그래프이다. 다익스트라 알고리즘을 사용하기 위해 모든 점의 거리를 inf로 설정한다.

 

문제에서 시작점도 계산하므로 distances [0][0]을 1로 설정한다.

 

queue에는 [거리, [현재점 위치]]의 형식으로 저장한다. [distance, [n, m]] 따라서 처음 점 (0, 0)에서 시작하므로 [1, [0, 0]]을 queue에 넣는다.

 

dn과 dm은 N과 M이 상하좌우를 참조한다. 상(n-1, m), 하(n+1, m), 좌(n, m-1), 우(n, m+1) 이므로 dn과 dm에 순서대로 넣는다. for문으로 계산하기 위함

 

queue가 빌 때 까지 while문을 반복한다.

 

queue에서 거리, 현재 좌표를 받아온다. currnet_distance, current_n, current_y에 저장한다.

 

만약 현재 거리가 distances에 저장된 거리보다 크다면 무시한다.

 

작은 경우 for문을 통해서 상, 하, 좌, 우 좌표의 값을 확인하여 1과 같으면 갈 수 있는 길이므로, 새로운 거리를 계산한다. 이 거리가 distances의 거리보다 짧다면, 값을 경신하고, 해당 좌표와 거리를 queue에 넣어준다. 

 

while문이 끝나면 출력 값인 distances [N-1][M-1]을 반환한다.

<입력>

 

N, M = map(int, sys.stdin.readline().split())

graph = []

for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip('\n'))))

print(dijkstra(graph, N, M))

 

N개 줄과 M개의 정수를 입력받는다.

graph를 선언해주고, N개 줄의 입력을 받는다.

반환된 distances [N-1][M-1]를 출력한다.

 

<전체 코드>

import sys
import heapq


def dijkstra(graph, N, M):
    distances = [[float('inf') for _ in range(M)] for _ in range(N)]

    distances[0][0] = 1

    queue = [[1, [0, 0]]]

    # 상하좌우
    dn = [-1, 1, 0, 0]
    dm = [0, 0, -1, 1]

    while queue:
        current_distance, current = heapq.heappop(queue)
        current_n, current_m = current

        if current_distance > distances[current_n][current_m]:
            continue

        for i in range(4):
            n = current_n+dn[i]
            m = current_m+dm[i]
            if 0 <= n < N and 0 <= m < M and graph[n][m] == 1:
                new_distance = current_distance+1

                if new_distance < distances[n][m]:
                    distances[n][m] = new_distance

                    heapq.heappush(queue, [new_distance, [n, m]])

    return distances[N-1][M-1]


N, M = map(int, sys.stdin.readline().split())

graph = []

for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip('\n'))))

print(dijkstra(graph, N, M))