[백준 4485번] 녹색 옷 입은 애가 젤다지?

# 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)
# '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다

# 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다
# 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다

# 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다

# 링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

import sys
from collections import deque

input = sys.stdin.readline

dx = [-1,1,0,0]
dy = [0,0,-1,1]

INF = float("inf")

index = 0

while True:
    n = int(input())

    index += 1

    if n == 0:
        break

    def bfs():
        area = [list(map(int,input().split())) for _ in range(n)]
        visited = [[INF]*n for _ in range(n)]

        visited[0][0] = area[0][0]

        queue = deque([(0,0)])

        while queue:
            x, y = queue.popleft()

            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]

                if not (0 <= nx < n and 0 <= ny < n):
                    continue

                if visited[nx][ny] == INF:
                    visited[nx][ny] = visited[x][y] + area[nx][ny]
                    queue.append((nx,ny))
                
                else:
                    if visited[x][y] + area[nx][ny] < visited[nx][ny]:
                        visited[nx][ny] = visited[x][y] + area[nx][ny]
                        queue.append((nx,ny))
        
        return visited[n-1][n-1]
    
    print(f"Problem {index}: {bfs()}")

 

이번 문제는 (0,0)에서 (n-1,n-1)까지 도착하기까지의 최소 거리를 구하는 문제이다.

 

처음에는 DFS와 백트래킹을 활용하여 풀이하려고 했었는데, 계속해서 시간초과가 발생하여 다른 분들의 풀이를 참고하게 되었다.

 

[SWEA - D4] 보급로

결국 이 문제는 다익스트라나 BFS를 활용하여 풀어야하는 문제인데, 이전에 SWEA에서 풀었던 문제와 동일한 내용의 문제이다.

 

(DFS를 사용해서 풀이하게 되면 N x N개의 좌표에서 매번 상하좌우를 선택할 수 있기 때문에 시간복잡도가 O(4^(N^2))가 된다.)

 

처음에 BFS로 풀이할 때는 visited 배열을 모두 True/False로 저장했었는데, 이렇게 저장하니 해당 좌표까지 갈 수 있는 최솟값을 구할 수 없고 한번 방문처리한 좌표는 다시 접근할 수 없다는 치명적인 문제점이 있었다.

 

따라서 다익스트라 알고리즘의 아이디어와 비슷하게, BFS로 모든 영역을 한번만 탐색(O(N^2))하면서 이미 방문한 지점이더라도 '현재 까지의 시간 + 비용'이 '이미 방문한 지점'보다 비용이 적다면, 이를 갱신해주는 방식으로 풀이할 수 있다. 

 

1. 함수 내에서 첫 방문일 때는 (현 위치까지의 최솟값 visited[x][y] + 다음 위치 A[nx][ny]) 해준 값으로 저장하고 큐에 담았다.
2. 이미 방문한 적이 있다면, 해당 위치를 최솟값으로 갱신할 수 있을 때만 (현 위치까지의 최솟값 + 다음 위치 값)을 저장하고 또 검사해주기 위해 큐에 담아줬다.
3. 큐에 있는 모든 원소에 대한 검사가 끝나 while문이 끝나면 visited가 해당 위치까지 갈 수 있는 최솟값을 의미하므로 목적지인 visited[nx][ny]에 있는 값을 리턴하고 출력한다.