18352 - 파이썬

 

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

18352번: 특정 거리의 도시 찾기

---

내 풀이

from collections import deque
import sys

input = sys.stdin.readline

N,M,K,X = map(int,input().split())
graph=[[] for _ in range(N+1)]
distance = [-1] * (N+1)
distance[X] = 0

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




q = deque([X])

while q:
    now = q.popleft()
    for next in graph[now]:
        if distance[next]==-1:
            distance[next] = distance[now] + 1
            q.append(next)

check = False

for i in range(1,N+1):
    if distance[i] == K:
        print(i)
        check=True

if check == False:
    print(-1)

 

---

이 문제의 핵심은 모든 간선의 비용이 1이라는 점이다. BFS는 모든 간선의 비용이 1일 때만 사용가능하다.

그래프에서 N이 아니라 N+1을 받은 이유는 1부터 시작한다는 점에서 직관성을 높여주려고 1부터 N까지 이용하였다.

애초에 1부터 차례차례로 확인하기 때문에 정렬이 필요없다.

참고로 그냥 input()으로 받으면 시간초과난다.

---

다른사람의 풀이

 

from collections import deque
import sys
f = sys.stdin.readline

n, m, k, x = map(int, f().split())
graph = [[] for _ in range(n+1)]
distance = [0] * (n+1)
visited = [False] * (n+1)

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

def bfs(start):
    answer = []
    q = deque([start])
    visited[start] = True
    distance[start] = 0
    while q:
        now = q.popleft()
        for i in graph[now]:
            if not visited[i]:
                visited[i] = True
                q.append(i)
                distance[i] = distance[now] + 1
                if distance[i] == k:
                    answer.append(i)
    if len(answer) == 0:
        print(-1)
    else:
        answer.sort()
        for i in answer:
            print(i, end='\n')

bfs(x)

---

---