[파이썬] 코딩테스트 14 구현_최단거리 ☆

문제

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

---

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

 

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

입력

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

출력

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

예제 입력 1

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

예제 출력 1

4

예제 입력 2

4 3 2 1
1 2
1 3
1 4

예제 출력 2

-1

예제 입력 3

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

예제 출력 3

2
3

출처

• 데이터를 추가한 사람: ajtwlstmdgks
• 문제를 만든 사람: ndb796

---

문제 요약

어떤 나라에 N개의 도시와 M개의 단방향 도로가 있다.

모든 도로의 거리는 1로 동일하다.

어떤 특정한 출발 도시 X에서 출발해, 도달할 수 있는 모든 도시 중에서

최단 거리가 정확히 K인 도시들을 찾아 오름차순으로 출력하는 문제다.

조건 요약

• 도시 개수: N (1 ≤ N ≤ 300,000)
• 도로 개수: M (1 ≤ M ≤ 1,000,000)
• 거리 정보: 모두 1
• 탐색 기준 거리: K
• 출발 도시: X

---

이 문제는 어떤 문제인가?

• 단방향 그래프 + 모든 간선의 가중치가 1
• → 즉, 최단 거리 문제이면서,
  간선의 가중치가 전부 동일하므로 **BFS(너비 우선 탐색)**으로 효율적으로 풀 수 있다.

---

입력 예시

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

• 도시 개수: 4
• 도로 개수: 4
• 목표 거리: 2
• 출발 도시: 1

---

해결 순서

1단계. 입력값 받기

n, m, k, x = map(int, input().split())

---

2단계. 그래프 정보 저장 (인접 리스트)

먼저 질문!

도시는 1번부터 N번까지 있어.

어떤 도시는 다른 도시로 길이 있을 수도 있고, 없을 수도 있음.

예를 들어, "1번 도시에서 2번 도시로 가는 길이 있다"

이런 정보를 프로그램 안에 어떻게 저장할 수 있을까?

 

이걸 해결하는 방법 중 하나가 바로 **"그래프(지도)를 코드로 만드는 것"**.

그중에서도 인접 리스트 방식이라는 걸 사용

---

그래프를 리스트로 저장?

그래프를 저장할 때는 도시별로 갈 수 있는 도시들을 모아두면 됨.

예를 들어, 이런 정보가 있다고 해보자:

코드 복사
1번 도시 → 2번 도시
1번 도시 → 3번 도시
2번 도시 → 4번 도시

이걸 코드 안에 이렇게 저장할 수 있음:

graph[1] = [2, 3]   # 1번 도시는 2번과 3번으로 갈 수 있다
graph[2] = [4]      # 2번 도시는 4번으로 갈 수 있다

---

실제 코드 설명

코드 전체

graph = [[] for _ in range(n + 1)]

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

이게 도로 정보를 저장하는 코드

---

첫 번째 줄: 

graph = [[] for _ in range(n + 1)]

 

도시가 n개 있으니까, n+1개의 리스트를 만들겠다는 의미

왜 +1을 하냐면?

→ 도시는 1번부터 시작하는데, 파이썬의 리스트는 0번부터 시작하니까,

0번은 그냥 비워두고, 1번부터 n번까지 쓰기 위해

예를 들어 n = 4라면:

graph = [ [], [], [], [], [] ]
#         0   1   2   3   4

• graph[1] : 1번 도시에서 갈 수 있는 도시 목록
• graph[2] : 2번 도시에서 갈 수 있는 도시 목록
• ...

아직 아무것도 입력 안 했기 때문에, 도시별로 빈 리스트가 들어있어.

---

두 번째 줄: 

for _ in range(m):

• 도로가 총 몇 개 있는지 = m개
• 도로 정보를 m번 입력 받겠다는 뜻이야.
• _는 그냥 반복문 안에서 사용하지 않을 변수일 때 쓰는 관습적인 표현이야.

예: 도로가 4개라면 → 이 반복문은 4번 돌게 됨

---

세 번째 줄: 

s, e = map(int, input().split())

이 줄은 도로 정보 하나를 입력받는 부분

• 사용자가 "1 2" 라고 입력하면
  • s = 1, e = 2가 됨
  • 즉, 1번 도시에서 2번 도시로 가는 길이라는 의미

예시 입력:

1 2
1 3
2 4

---

네 번째 줄: 

graph[s].append(e)

이 줄이 핵심!!

• s번 도시에서 e번 도시로 갈 수 있다는 정보를 저장하는 줄
• graph[s]는 s번 도시에서 갈 수 있는 도시들을 모아둔 리스트
• append(e)는 그 리스트에 e를 추가하겠다는 뜻

예를 들어, 앞에서 입력한 정보들이 들어오면:

1 2   →  graph[1] = [2]
1 3   →  graph[1] = [2, 3]
2 4   →  graph[2] = [4]

---

최종 예시로 확인

입력이 이렇게 들어왔을 때:

n = 4
m = 3
입력:
1 2
1 3
2 4

실행된 후 graph는 이렇게 생김:

graph = [
    [],         # 0번 도시는 없음
    [2, 3],     # 1번 도시는 2번, 3번으로 갈 수 있음
    [4],        # 2번 도시는 4번으로 갈 수 있음
    [],         # 3번 도시는 아무 곳도 못 감
    []          # 4번 도시도 아무 곳도 못 감
]

---

정리

코드	뜻
graph = [[] for _ in range(n + 1)]	도시 개수만큼 빈 리스트 준비 (인접 리스트 구조)
for _ in range(m):	도로 정보 개수만큼 반복
s, e = map(int, input().split())	출발 도시(s), 도착 도시(e) 입력 받기
graph[s].append(e)	출발 도시에서 도착 도시로 가는 길 저장

 

---

3단계. BFS로 최단 거리 구하기

BFS를 사용하면 출발점으로부터의 최단 거리를 구할 수 있다.

거리를 저장할 리스트 distance를 만들고, 방문 여부와 거리 정보를 함께 저장한다.

초기값은 모두 무한대(= 아직 방문하지 않음), 출발 도시는 0이다.

from collections import deque

def bfs(start):
    INF = float("inf")
    distance = [INF] * (n + 1)
    q = deque()

    q.append(start)
    distance[start] = 0  # 시작 도시는 거리 0

    while q:
        now = q.popleft()

        for next_node in graph[now]:
            if distance[next_node] == INF:  # 아직 방문 안한 도시
                distance[next_node] = distance[now] + 1
                q.append(next_node)

    return distance

---

4단계. 거리 K인 도시만 출력하기

distance 배열에서 값이 k인 도시만 골라낸다.

→ enumerate를 활용하면 인덱스(도시 번호)를 함께 가져올 수 있다.

result = bfs(x)
answer = [i for i, d in enumerate(result) if d == k]

if not answer:
    print(-1)
else:
    answer.sort()  # 오름차순 정렬
    for city in answer:
        print(city)

---

전체 코드

from collections import deque

n, m, k, x = map(int, input().split())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    s, e = map(int, input().split())
    graph[s].append(e)

def bfs(start):
    INF = float("inf")
    distance = [INF] * (n + 1)
    q = deque()

    q.append(start)
    distance[start] = 0

    while q:
        now = q.popleft()
        for next_node in graph[now]:
            if distance[next_node] == INF:
                distance[next_node] = distance[now] + 1
                q.append(next_node)
    return distance

result = bfs(x)
answer = [i for i, d in enumerate(result) if d == k]

if not answer:
    print(-1)
else:
    answer.sort()
    for city in answer:
        print(city)

---

핵심 정리

• 간선 가중치가 모두 1인 최단 거리 문제 → BFS가 가장 적절하다.
• BFS를 사용할 때, 방문 여부를 거리 리스트로 함께 관리하면 효율적이다.
  • 초기값은 모두 무한대
  • 출발점은 거리 0
  • 새로 방문할 때는 현재 거리 + 1로 갱신
• 결과로 나온 거리 배열에서 거리 K인 도시만 추출하면 된다.