문제
구름이가 사는 구름 나라는 N개의 섬으로 이루어져 있다. 각 섬에는 1부터 N까지의 번호가 붙어 있고, 구름 나라는 사람들이 섬과 섬 사이를 편하게 이동할 수 있도록 다리를 M개 설치했다. 설치된 다리들은 아래 특징들을 만족한다.
- 모든 다리는 단방향으로만 이동할 수 있다.
- 서로 다른 두 섬을 잇는 다리는 최대 하나이다.
- 다리가 잇는 두 섬은 항상 다른 섬이다.
구름이는 현재 K번 섬에 있고, 다른 섬들을 둘러본 뒤 다시 K번 섬으로 돌아오려고 한다. 그렇지만 오래 돌아다니는 것은 피곤한 일이기 때문에, 구름이는 최소한의 다리만 거치는 경로를 택할 것이다. 구름이를 도와 최소 몇 개의 다리를 거쳐서 원래 구름이가 있던 섬으로 돌아올 수 있을지 알아보자. 다시 돌아올 수 있는 경로가 없는 경우에는 -1을 출력한다.
단, 구름이는 K번 섬 이외의 최소 하나 이상의 다른 섬을 방문해야 한다.
입력
첫째 줄에 섬의 개수 N과 다리의 개수 M, 그리고 구름이가 있는 섬의 번호 K가 공백을 두고 주어진다.
다음 M개의 줄에는 다리의 시작 섬과 도착 섬을 의미하는 a, b가 공백을 두고 주어진다.
- 2 ≤ N ≤ 10,000
- 1 ≤ M ≤ 50,000
- 1 ≤ K ≤ N
- 1 ≤ a, b ≤ N : a ≠ b
- 서로 다른 두 다리의 시작 섬과 도착 섬이 같은 경우는 없다.
- 입력에서 주어지는 모든 수는 정수이다.
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):
start, arrive = map(int, input().split())
conn[start].append(arrive)
q = deque()
q.append(k)
visited = [9**9] * (n+1)
visited[k] = 0
result = 9**9
while q:
cur_node = q.popleft()
count = 0
for next_node in conn[cur_node]:
if next_node == k:
result = min(result, visited[cur_node] + 1)
if visited[next_node] <= visited[cur_node]+1:
continue
visited[next_node] = visited[cur_node] + 1
q.append(next_node)
if result == 9**9:
print(-1)
else:
print(result)이번 문제는 지난 번 구름이의 여행 문제에서 조건문 하나만 더 추가를 해주면 해결되는 문제였다.
양방향이 아닌 단방향이니 처음 딕셔너리 설정도 시작 점과 끝 점만 저장을 해주면 알아서 단방향으로 정리가 된다.
각 노드(섬)을 순회하다가 처음 출발지점(k)을 만난다면, 이전 노드(섬)까지 가는 방법에 +1 만 하면 된다.
만약 처음 출발지점(k)을 만나지 못했다면 결과 값은 처음 설정했던 값이 그대로이기 때문에 나중에 결과 값을 봤을 때 처음 출발지점을 만났는지 안 만났는지를 알 수 있다.
※출처
https://multicampus-kdt.goorm.io/lecture/38996/멀티잇-코딩테스트-러닝클래스-python-6월반