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

백준 4485_녹색 옷 입은 애가 젤다지?

시간제한 1초, 메모리제한 256MB

# 조건

• 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다.
• 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!
• 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다.
• [0][0]번 칸이기도 하다.
  • 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다.
  • 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.
• 하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다.
• 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다.
• 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

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

입력

• 입력은 여러 개의 테스트 케이스로 이루어져 있다.
• 각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125)
• N = 0인 입력이 주어지면 전체 입력이 종료된다.
• 이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다.
• 도둑루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다.
  • 여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.

# 접근 방법

시간초과

• bfs를이용하여 풀어준다.
• 상하좌우 인접한 칸을 deque에 넣어주며, visited 배열에 최소값을 기록해준다.
  • 이 때, visited가 방문되지 않았거나, 아래와 같이 갱신해줄 수 있다면 방문 가능한 곳이다.
• 즉, 0,0은 5가 되며, 1,0은 8이되고, 0,1은 10이라고 가정하자.
• 이 때, 1,1은 13 < 18 이므로 13으로 갱신해준다.

from collections import deque  
import sys  
sys.stdin = open('input.txt')  

di, dj = [1,-1,0,0], [0,0,1,-1]  

def bfs(si, sj):  
    visited = [[0]*N for _ in range(N)]  
    q = deque()  
    q.append((si, sj))  
    visited[si][sj] = arr[0][0]  
    while q:  
        sti, stj = q.popleft()  
        for i in range(4):  
            ni, nj = di[i] + sti, dj[i] + stj  
            # 우선 범위 내라면  
            if 0<=ni<N and 0<=nj<N:  
                # 방문하지 않았다면  
                if visited[ni][nj] == 0:  
                    q.append((ni, nj))  
                    visited[ni][nj] = visited[sti][stj] + arr[ni][nj]  
                else:  
                    if visited[ni][nj] > arr[ni][nj] + visited[sti][stj]:  
                        q.append((ni, nj))  
                        visited[ni][nj] = arr[ni][nj] + visited[sti][stj]  

    return visited[N-1][N-1]  

cnt = 1  
while True:  
    N = int(input())  
    if N == 0:  
        break  
    arr = [[*map(int, input().split())] for _ in range(N)]  
    result = bfs(0,0)  
    print(f'Problem {cnt} : {result}')  
    cnt += 1

정답 풀이

• 최단 거리를 구하는 것과 마찬가지이므로, 그래프로 풀어준다.
  • 방문가능한 곳이라면 - 연결되어 있다면 - 가중치와 함께 heappush 해준다.
• heapq를 사용하여 다익스트라로 풀어준다면 시간이 O((v+e)log(v))가 되어 시간초과 없이 해결가능

from heapq import heappop, heappush  
import sys  

INF = 200000000  
di, dj = [1,-1,0,0], [0,0,1,-1]  


def bfs(graph):  
    dist = [[INF] * N for _ in range(N)]  
    dist[0][0] = graph[0][0]  
    q = []  
    heappush(q, (graph[0][0], 0,0))  
    while q:  
        val, si, sj = heappop(q)  
        if dist[si][sj] < val:  
            continue  
        for i in range(4):  
            ni = si + di[i]  
            nj = sj + dj[i]  
            if 0<= ni < N and 0<= nj < N:  
                if val + graph[ni][nj] < dist[ni][nj]:  
                    dist[ni][nj] = val + graph[ni][nj]  
                    heappush(q, (dist[ni][nj], ni, nj))  

    return dist[-1][-1]  
cnt = 1  
while True:  
    N = int(input())  
    if N == 0:  
        break  
    graph = []  
    for i in range(N):  
        graph.append([*map(int, input().split())])  
    result = bfs(graph)  
    print(f'Problem {cnt}: {result}')  
    cnt += 1