백준 18352 특정 거리의 도시 찾기 | BFS와 distance 배열 풀이

백준 18352는 그냥 BFS 최단거리 문제다.

모든 도로 길이가 1이라서 다익스트라까지 갈 필요 없고,

출발 도시 X에서 BFS 한 번 돌린 뒤 distance 배열에서 값이 K인 도시만 뽑으면 끝난다.

문제 자체는 어렵지 않은데,

막상 구현할 때는 여기서 한 번씩 꼬인다.

• distance 배열을 어떻게 둘지
• 방문 체크를 따로 할지 같이 할지
• 큐를 리스트로 할지 deque로 할지
• 거리 갱신을 뭘 기준으로 할지

나도 처음엔 방향은 맞게 잡았는데

거리 갱신을 잘못 잡아서 한 번 틀어졌다.

그래서 이 문제는 정답만 보는 것보다, BFS 거리 문제를 어떻게 구현하는지 정리해두는 게 더 중요했다.

---

문제 정리

문제 조건은 이렇다.

• 도시가 N개 있다
• 도로가 M개 있다
• 도로는 방향성이 있다
• 모든 도로 길이는 1
• 출발 도시 X에서 **최단거리 정확히 K*인 도시를 출력한다
• 없으면 1 출력

여기서 바로 봐야 하는 건 두 개다.

• 최단거리
• 모든 간선 가중치가 1

이 조합이면 BFS로 가는 게 맞다.

---

🔗 문제 링크

백준 18352 - 특정 거리의 도시 찾기

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

---

정답

from collections import deque

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

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

distance = [-1] * (n + 1)
distance[x] = 0

q = deque([x])

while q:
    now = q.popleft()

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

result = []
for city in range(1, n + 1):
    if distance[city] == k:
        result.append(city)

if result:
    for city in result:
        print(city)
else:
    print(-1)

---

생각해야 하는 부분

이 문제는 BFS만 떠올리면 끝나는 게 아니다.

정확히는 BFS + distance 배열 설계가 핵심이다.

1. 왜 DFS가 아니라 BFS인가

이 문제는 “최단거리 K”를 묻는다.

DFS는 깊게 들어갔다가 돌아오는 구조라서

“출발점에서 몇 단계 떨어졌는지”를 깔끔하게 관리하기 불편하다.

반면 BFS는

• 1칸 떨어진 도시
• 2칸 떨어진 도시
• 3칸 떨어진 도시

이렇게 레벨 순서대로 탐색하니까

최단거리 문제와 바로 연결된다.

즉, 이 문제는 거리 문제라서 BFS다.

---

2. 왜 distance 배열을 따로 두는가

이 문제에서 distance 배열은 그냥 거리 저장용이 아니다. 사실상 방문 체크 + 최단거리 기록을 같이 한다.

distance = [-1] * (n + 1)
distance[x] = 0

이 구조로 가면 의미가 명확하다.

• 1 → 아직 방문 안 함
• 0 이상 → 방문했고, 그 값이 최단거리

처음엔 방문 리스트를 따로 둘까 싶었는데,

이 문제는 distance 하나로 끝내는 게 제일 깔끔했다.

---

3. 거리 갱신 기준은 “도시 번호”가 아니라 “이전 거리”다

이 문제에서 제일 중요한 줄은 이거다.

distance[nxt] = distance[now] + 1

핵심은 도시 번호가 아니라

출발점에서 현재 도시까지의 거리다.

즉,

• now가 몇 번 도시인지는 중요하지 않고
• now까지 몇 칸 왔는지가 중요하다

그래서 다음 도시는 항상 +1로 갱신된다.

---

4. 왜 deque를 쓰는가

BFS니까 큐가 필요하다.

파이썬에서는 큐가 필요하면 그냥 deque 쓰는 게 맞다.

from collections import deque

q = deque([x])
now = q.popleft()

리스트로 pop(0) 해도 돌아가긴 하는데,

앞에서 계속 꺼내는 구조라 비효율적이다.

이 문제는 입력 크기도 있어서

괜히 리스트 큐로 버티는 것보다 deque로 가는 게 낫다.

---

예외처리 / 구현할 때 주의할 점

⚠️ 1. 방향 그래프다

이 문제는 도로가 방향성을 가진다.

graph[a].append(b)

여기서 graph[b].append(a)까지 넣으면

양방향 그래프가 돼서 완전히 다른 결과가 나온다.

---

⚠️ 2. 도시 번호는 1번부터 시작한다

그래서 배열 길이는 n + 1로 두는 게 맞다.

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

이걸 n으로 잡으면 인덱스가 바로 꼬인다.

---

⚠️ 3. 정답은 방문 순서가 아니라 거리 K인 도시다

BFS를 돌고 나서

방문한 순서 출력하는 문제가 아니다.

마지막에는 반드시

for city in range(1, n + 1):
    if distance[city] == k:
        print(city)

이렇게 distance 값을 보고 판단해야 한다.

---

내 시행착오

이 문제에서 내가 처음 틀린 건 방향이 아니라 구현 디테일이었다.

1. distance 배열을 이상하게 만들었다

처음엔 거리 배열을 문자열처럼 잡으려고 했다.

dis = [f'inf({i})' for i in range(n)]

지금 보면 거리 배열이 아니라 그냥 문자열 리스트다.

이건 비교도 안 되고, 갱신도 이상해진다.

결국 이 문제는 숫자로 가야 해서

• 1 초기화가 제일 깔끔했다.

---

2. 큐를 리스트로 두고 pop(0)을 썼다

todo = []
todo.append(x)
now = todo.pop(0)

동작은 할 수 있는데,

이 방식은 BFS 구현할 때 계속 찝찝하다.

앞에서 꺼내는 일이 반복되니까

그냥 deque.popleft()로 가는 게 맞다.

---

3. 거리 갱신을 도시 번호 기준으로 생각했다

처음엔 이런 식으로 꼬였다.

dis[now] = now + 1

근데 이건 도시 번호에 1 더한 거지,

최단거리가 아니다.

이 문제는

“지금 몇 번 도시냐”가 아니라

“출발점에서 몇 칸 떨어져 있냐”를 기록해야 한다.

즉, 도시 번호랑 거리 개념을 섞으면 바로 틀어진다.

---

한 줄 정리

이 문제는 BFS 거리 문제의 기본형이다. 핵심은 BFS 자체보다 distance 배열을 방문 여부 + 최단거리 기록용으로 같이 쓰는 것이다.