[백준] 18352번 : 특정 거리의 도시 찾기

출처 : 이것이 취업을 위한 코딩테스트다 with python

문제 : https://www.acmicpc.net/problem/18352

 

유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 다익스트라

 

1. 문제

예시

4 4 2 1
1 2
1 3
2 3
2 4

예시 출력

4

---

2. 풀이

## 백준 18352 : 특정 거리의 도시 찾기
# 이것이 취업을 위한 코딩테스트다 with python
import sys
from collections import deque

input = sys.stdin.readline
n,m,k,x = map(int, input().split())
graph = [[] for _ in range(n+1)] # 데이터를 처음 0번째부터 넣지 않고 1번쨰부터 넣기 떄문에

for _ in range(m):
    a,b = map(int, input().split())
    graph[a].append(b)

dis = [-1] * (n+1)
dis[x] = 0 # 시작 도시 -> 시작 도시 거리는 0

q = deque([x])

while q:
    now = q.popleft()
    for next in graph[now]:
        if dis[next] == -1: # 방문x
            dis[next] = dis[now] + 1
            q.append(next)

check = False
for i in range(1,n+1):
    if dis[i] == k:
        print(i)
        check = True

if check == False:
    print(-1)

이 문제는 주어진 최단 거리에 있는 도시를 찾는 문제이기 때문에, 너비우선탐색인 BFS를 이용하면 된다. 그리고 sys.stdin.readline으로 해야 python으로 제출했을 때 문제 없이 제출이 된다고 해서 추가하였다.