문제
구름이가 사는 나라는 N개의 섬으로 이루어져 있다. 각 섬에는 1부터 N까지의 번호가 붙어 있고, 각 섬마다 편하게 이동할 수 있도록 다리를 M개 설치했다. 설치된 다리들은 아래 특징들을 만족한다.
- 모든 다리는 양방향으로 이동할 수 있다.
- 서로 다른 두 섬을 잇는 다리는 최대 하나이다.
- 다리가 잇는 두 섬은 항상 다른 섬이다.
구름이는 1번 섬에서 출발해서 N번 섬으로 가려고 하는데, 통과하는 다리의 개수가 K개 이하가 되길 원한다. 구름이를 도와 1번 섬에서 N번 섬까지 K개 이하의 다리를 이용해 도착할 수 있는지를 판별해보자.
입력
첫째 줄에 섬의 개수 N과 다리의 개수 M, 그리고 구름이가 건널 다리의 최대 개수 K가 공백을 두고 주어진다.
다음 M개의 줄에는 다리가 잇는 두 섬의 번호를 의미하는 ui, vi 가 공백을 두고 주어진다.
- 2 ≤ N ≤ 1,000
- 1 ≤ M ≤ 5,000
- 1 ≤ K ≤ M
- 1 ≤ ui, vi ≤ N : ui ≠ vi
- 서로 다른 두 섬 사이를 잇는 다리는 최대 하나이다.
- 입력에서 주어지는 모든 수는 정수이다.
출력
구름이가 1번 섬에서 N번 섬까지 K개 이하의 다리를 사용해서 갈 수 있다면 YES, 갈 수 없다면 NO를 출력한다.
from collections import defaultdict
from collections import deque
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
conn = defaultdict(list)
for _ in range(m):
u, v = map(int, input().split())
conn[u].append(v)
conn[v].append(u)
q = deque()
q.append(1)
visited = [9**9 for _ in range(n+1)]
visited[1] = 0
while q:
cur_node = q.popleft()
for next_node in conn[cur_node]:
if visited[next_node] <= visited[cur_node] + 1:
continue
q.append(next_node)
visited[next_node] = visited[cur_node] + 1
print(visited)
if visited[n] <= k:
print("YES")
else:
print("NO")처음에 각 섬을 key로 두고, value 값은 key값과 이어지는 번호를 리스트로 정리해둔다.
그리고 해당 딕셔너리로 deque 를 이용해 처음 key의 value 값을 이용해서 방문하지 않은 섬이면 deque 에 넣는다.
각 노드끼리의 거리는 비용이 없는 1라고 판단하고 방문하지 않은 섬이면 이전 섬+1 의 값을 넣어 해당 섬까지의 방법이 몇개인지 계산한다.
최종 목표 섬까지의 거리가 문제 요구사항과 비교해서 값을 출력하면 끝.
그래프 문제를 제대로 접한것은 이번이 처음이라 이해하기까지 많은 시간이 걸렸다.
그러나 한 번 이해하니 코드를 싹 다 지우고 다시 풀으라고 해도 다시 풀 수 있을 간단한 문제였다.
※출처
https://multicampus-kdt.goorm.io/lecture/38996/멀티잇-코딩테스트-러닝클래스-python-6월반
