백준 4485: 녹색 옷 입은 애가 젤다지? Python (Dijkstra)

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

4485번: 녹색 옷 입은 애가 젤다지?

 

 

이 문제는 최소 거리를 구하는 알고리즘을 사용하면 된다.

처음에는 dfs를 사용했다.

import sys
input = sys.stdin.readline  # 연산처리 속도 줄이기 위해


def dfs(arr, si, sj, end, tot):
    global min_value
    # 종료조건
    if tot > min_value:
        return
    if (si, sj) == (end, end):
        if tot < min_value:
            min_value = tot
            return
    # 재귀
    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:   # 상, 하, 좌, 우
        ni, nj = si+di, sj+dj
        if 0 <= ni <= end and 0 <= nj <= end and not visited[ni][nj]:
            visited[ni][nj] = 1
            dfs(arr, ni, nj, end, tot+arr[ni][nj])
            visited[ni][nj] = 0


cnt = 1
while True:
    N = int(input())
    if N == 0:  # 종료 조건
        break
    cave = [list(map(int, input().split())) for _ in range(N)]
    min_value = 987654321
    visited = [[0] * N for _ in range(N)]
    dfs(cave, 0, 0, N-1, cave[0][0])
    print(f'Problem {cnt}:', min_value)
    cnt += 1

 

이렇게 하면 시간초과가 계속 난다. DFS는 재귀 방식이기 때문에 (대부분의 경우) 입력 사이즈가 최대 20까지일 때 버텨줄 수 있다.

근데 지금은 동굴의 크기인 N이 2 ≤ N ≤ 125이기 때문에 dfs 대신 다른 방식을 사용해야 한다.

 

bfs나 dijkstra 둘 다 가능한데 이번에는 dijkstra를 썼다.

import sys, heapq
input = sys.stdin.readline  # 연산처리 속도 줄이기 위해
INF = sys.maxsize


def dijkstra(arr, end):
    queue = []
    dist[0][0] = arr[0][0]
    heapq.heappush(queue, (dist[0][0], 0, 0))

    while queue:
        now = heapq.heappop(queue)
        if (now[1], now[2]) == (end, end):
            return dist[end][end]
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # 상, 하, 좌, 우
            ni, nj = now[1]+di, now[2]+dj
            if 0 <= ni <= end and 0 <= nj <= end and dist[ni][nj] > arr[ni][nj] + now[0]:
                dist[ni][nj] = arr[ni][nj] + now[0]
                heapq.heappush(queue, (dist[ni][nj], ni, nj))


cnt = 1
while True:
    N = int(input())
    if N == 0:  # 종료 조건
        break
    cave = [list(map(int, input().split())) for _ in range(N)]
    dist = [[INF]*N for _ in range(N)]  # 거리 구하기
    print(f'Problem {cnt}:', dijkstra(cave, N-1))
    cnt += 1