BOJ - 18352

백준 문제 링크
특정 거리의 도시 찾기

❓접근법

1. BFS를 사용했다.
2. 단방향 도로임을 주의하자
3. 자식 노드를 처음 방문할 경우
   자식 노드(i)의 count 값에 부모 노드(x)의 count 값 + 1을 넣어준다.
   answer[i] = answer[x] + 1
   visited로 방문처리하고, queue에 넣어준다.
4. 조건이 좀 까다로운데,
   1) 최단거리 K가 answer에 없을 때 -1을 출력
   2) 최단거리 K가 answer에 있을 때
   2-1) 출발하는 도시(X)와 현재 도시가 다를 때,
   현재 도시의 answer 값이 최단거리(K)와 같다면 answer[i]를 출력
   2-2) 출발하는 도시(X)와 현재 도시가 같을 때,
   현재 도시의 answer 값이 최단거리(K)와 같다면 -1을 출력
   이 조건에 대한 반례는 밑에 있다

<반례>
2 2 2 1
1 2
2 1

-1 이 출력되어야 한다.

👌🏻코드

from collections import deque
import sys

N,M,K,X = map(int, sys.stdin.readline().split())

lst = [[] for _ in range(N+1)]

for _ in range(M):
    x,y = map(int, sys.stdin.readline().split())일
    lst[x].append(y)

visited = [False] * (N+1)

answer = [0] * (N+1)

def bfs(x):
    queue = deque()
    queue.append(x)
    
    while queue:
        v = queue.popleft()
        
        for i in lst[v]:
            if not visited[i]:
                visited[i] = True
                answer[i] = answer[v] + 1
                queue.append(i)

bfs(X)

if K in answer:
    for i in range(len(answer)):
        if i != X:
            if answer[i] == K:
                print(i)
        else:
            if answer[i] == K:
                print(-1)
            
else:
    print(-1)