📖Problem

🔍Intuition

<aside> 💡 최단거리를 구하는 문제 ⇒ BFS로 접근한다!

</aside>

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

• 모든 도로의 거리: 1, 단방향 도로
• N: 도시의 개수, M: 도로의 개수, K: 최단거리, X: 출발도시 번호
• 출발도시로부터 최단거리 K에 위치하는 도시 번호 출력

🔍Approach

1. 도시의 개수 N, 도로의 개수 M, 최단거리 K, 출발도시 번호 X를 입력받고, 방문여부를 판단하는 visited 리스트와 그래프로 표현할 graph 리스트, 정답을 저장할 answer 리스트를 초기화한다. 이때 visited 리스트는 방문 여부를 판단할 뿐만 아니라 거리를 저장하는 역할로써 사용한다.
2. 그래프를 단방향으로 연결한다.
3. BFS 함수를 정의한다.
   1. queue를 deque 자료형으로 선언한다.
   2. queue가 있는 동안 아래 과정을 반복한다.
   3. 첫번째 노드를 pop하고, 해당 노드와 연결되어 있으며, 방문하지 않고, 첫번째로 시작한 노드가 아닌 연결된 노드라면, queue에 추가하고, 방문 표시를 한다. 이때 방문 표시는 현재 노드의 거리에 +1을 해준다.
   4. 동시에 만약 연결된 노드의 거리(visited[connected_node])가 최단거리 k와 같다면 answer 리스트에 추가한다.
4. BFS 함수를 호출하여 answer 리스트를 반환받는다.
5. answer리스트가 존재하지 않는 경우는 최단 거리 k인 도시가 하나도 존재하지 않는 경우이기 때문에 -1을 출력하고, 존재하는 경우에는 오름차순으로 정렬한 후 한 줄에 하나씩 출력한다.

🚩My submission

1차 시도 → 성공

import sys
from collections import deque

input = sys.stdin.readline

def bfs(start):
    global k
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for connected_node in graph[node]:
            # 해당 노드와 연결된 노드이고, 방문하지 않았을 경우 큐에 추가
            if visited[connected_node] == 0 and connected_node != start:
                queue.append(connected_node)
                visited[connected_node] = visited[node] + 1
                # 연결된 노드의 거리가 k와 같다면 answer 리스트에 추가
                if visited[connected_node] == k:
                    answer.append(connected_node)
    return answer

# 도시 개수 n, 도로 개수 m, 거리 정보 k, 출발도시 번호 x
n, m, k, x = map(int, input().strip().split())
visited = [0 for _ in range(n + 1)]
graph = [[] for _ in range(n + 1)]
answer = []
# 그래프 연결
for _ in range(m):
    u, v = map(int, input().strip().split())
    graph[u].append(v)

# BFS 호출 -> 출발도시 번호 x로 시작
answer = bfs(x)
if not answer:
    print(-1)
else:
    answer.sort()
    for u in answer:
        print(u)