[4485] 녹색 옷 입은 애가 젤다지?(python)

1. 문제

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

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

 

2. 풀이 과정

- (0,0) 에서 (N-1,N-1)까지 갈 때 최소 루피(비용)을 출력하는 문제

- 처음엔 다익스트라로 풀려 했는데, BFS로 풀게 되었다.

- 다익스트라는 "간선의 길이"가 중요한 문제, 즉 A번 -> C번 노드로 가는데 걸리는 "간선"의 비용이 어느정도인지가 주어지면 푸는 문제인데 해당 문제는 간선의 비용이 아니라 "특정 노드"에 도착했을 때 무조건 걸리는 비용이 주어졌으므로 BFS로 푸는게 더 낫다. 

- 또한, 다익스트라로 풀게 되면 각 좌표의 지점들을 모두 노드로 생각해서 풀어야 하므로, (0,0) , (0,1), (0,2)...(N-1,N-1)의 노드 개수(V)는 N&^2개, 간선 개수(E)는 N*N*(N-1)/2개가 된다.

- BFS로 풀게 되면 인접 행렬일 때 노드 개수는 V = N^2개가 된다. 

    * 다익스트라의 시간복잡도 : O(∣E∣log∣V∣)

    * BFS의 시간복잡도 : 인접 행렬일 때 O(∣V∣^2)

이므로, 다익스트라의 시간복 

 

3. 새로안 것 & 실수한 것 

- 파이썬은  매개변수로 인자를 넘기지  않아도 되는 경우가 있다

- from heapq import heappush, heappop으로 불렀으면 heappush, heappop으로 사용해야하고, 

import heapq로 불렀으면 heapq.heqppush, heapq.heappop으로 사용해야 한다.

 

4. 코드

#녹색 옷 입은 애가 젤다지?
#다익스트라는 간선 길이가 핵심( 특정 노드 사이의 거리)
#얜 간선의 길이가 아니라 그 "노드"로 가는 비용
#얘를 다익스트라로 N * M * 4(상하좌우) 크기로 넣어주어ㅑ 함

from heapq import heappush, heappop
import sys
input = sys.stdin.readline
INF = int(97654321)

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

def bfs():
    q = []
    heappush(q,(graph[0][0],0,0))
    distance[0][0] = 0

    while q:
        cost, x, y = heappop(q)

        if x == (N-1) and y == (N-1):
            print(f'Problem {cnt}: {distance[x][y]}')
            break

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            else:
                nc = cost + graph[nx][ny]
                
                if nc < distance[nx][ny]:
                    distance[nx][ny] = nc
                    heappush(q,(nc,nx,ny))

while True:
    N = int(input())
    if N == 0:
        break
    
    graph = [ list(map(int, input().split())) for _ in range(N)]
    distance = [ [INF] * N for _ in range(N)]
    bfs()
    cnt += 1