[백준 14619번] 파이썬 - 섬 여행

백준 14619 - 섬 여행

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

# 조건

• 취미가 여행이고 특기가 여행인 정우는 이번에는 여러 섬들을 여행해보려고 한다.
• 정우가 목적지로 잡은 섬은 총 N개이며 N개의 섬들은 M개의 양방향 통행 다리가 이어져 있어서 한 섬에서 다른 섬으로 이동할 수 있는 여러 경로가 존재한다.
• 정우는 섬의 지도를 보다가 지도에 적힌 섬의 높이를 보고 문득 이런 생각을 하게 된다.
• “어떤 섬 A에서 출발하여 K개의 다리를 이동하였을 때, 도착할 수 있는 높이가 가장 낮은 섬의 높이는 무엇일까?”
• 정우가 궁금해하는 문제를 대신 해결해주자!

입력

• 입력의 첫째 줄에 N, M(2 ≤ N ≤ 100, 1 ≤ M ≤ 10,000)이 공백으로 구분되어 주어진다.
• 입력의 둘째 줄에 N개의 섬의 높이 H(0 ≤ H ≤ 10,000)가 공백으로 구분되어 주어진다.
• 입력의 셋째 줄 부터 M개의 줄에 섬의 연결을 나타내는 정수 X, Y가 공백으로 구분 되어 주어진다.(1 ≤ X, Y ≤ N)
  • 이는 X, Y 두 섬이 양방향 통행 다리로 연결되어 있다는 의미다.
• 입력의 M+4째 줄에 정우가 궁금해하는 질의의 수 T(1 ≤ T ≤ 10,000)가 주어진다.
• 다음 T개의 줄에 현재의 위치 A(1 ≤ A ≤ N)와 이동해야 하는 다리의 수 K(1 ≤ K ≤ 500)가 주어진다.

출력

• 각 질의에 대해서 각 줄 마다 A번 섬에서 정확히 K번 이동하였을 때 도착 가능한 섬들의 높이 중 가장 낮은 섬의 높이를 출력한다.
• K번 이동하였을 때 도착 가능한 섬이 없을 경우 -1을 출력한다.

# 접근 방법

• 전형적인 DP 문제이다.
• DP[I][J]를 I번 섬에서 J번 건넜을 때 도착가능 한 가장 낮은 섬으로 사용해주며 탐색한다.
  • DP[I][J] = min[dp[i][j], dfs(i와 연결 지, K-1)]
  • 즉, a - b - c가 연결되어있다고 할 때, a에서 2번 이동하여 가장 낮은 섬이 c라면, b에서 1번 이동해서 가장 낮은 섬도 C이다.
• 우선 주어진 섬 간의 양방향 다리를 기록해준다.
• dp 배열을 큰 값으로 설정하여 생성해주고, 플로이드 - 워셜을 사용하여 최대 500의 이동을 하며 dp 값을 갱신해준다.
  • 플로이드 - 워셜을 사용하면 각 정점에서 다른 정점까지의 최소 값이 기록되므로 마지막에 입력된 출발점에서 K번째의 값을 구해주면 된다.
  • 마지막에 inf의 값이라면 -1을 출력해주는 처리를 해야한다.
• 다른 분들의 코드를 참고하면, dfs와 SPFA라는 벨만 - 포드를 업그레이드한 알고리즘을 사용해주는데
  • 갱신되는 점에 연결되어 있는 간선을 이용하여 정점에 대한 비용을 갱신할 , 큐에 없다면 그 정점을 넣어주는 방식이다

import sys  
sys.stdin = open('input.txt')  
input =sys.stdin.readline  


N, M = map(int, input().split())  
get_value = lambda x: int(x) -1  
dp = [[float('inf')] * 501 for _ in range(N)]  
height = list(map(int, input().split()))  
# 각 섬의 초기 높이 기
for i in range(N):  
    dp[i][0] = height[i]  
island = [[] for _ in range(N)]  

for _ in range(M):  
    a, b = map(get_value, input().split())  
    island[a].append(b)  
    island[b].append(a)  

# dp에 미리 기록해두기 
# 플로이드 워셜 활용
for i in range(1, 501):  
    for j in range(N):  
        temp = float('inf')  
        for v in island[j]:  
            temp = min(temp, dp[v][i-1])  

        dp[j][i] = temp  

for _ in range(int(input())):  
    a, k = map(int, input().split())  
    a -= 1  

    val = dp[a][k]  
    if val == float('inf'):  
        print(-1)  
    else:  
        print(val)