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

import heapq

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

for i in range(M):
    A, B = map(int, input().split())
    graph[A].append((B, 1))


def dijkstra(graph, start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            if dist + i[1] < distance[i[0]]:
                distance[i[0]] = dist + i[1]
                heapq.heappush(q, (dist + i[1], i[0]))


dijkstra(graph, X)
c=0
m=-1
for i in distance:
    c=c+1
    if i==K:
        m=0
        print(c-1)

if m==-1:
    print(-1)

 

🔍 문제 설명

N개의 도시와 M개의 도로가 존재하는 방향 그래프에서 출발 도시 X에서 출발해 거리 K인 도시를 찾는 문제입니다. 모든 도로의 거리는 1로 동일합니다.

---

🧠 접근 방법

• 다익스트라 알고리즘으로 X에서 모든 도시까지의 최단 거리 계산.
• 거리 배열을 확인해 거리 K인 도시를 필터링.
• 가중치가 모두 1이므로 BFS도 가능하지만, 다익스트라로 풀이.

---

📝 코드 설명

• INF를 크게 설정해 초기 거리 배열을 무한대로 초기화.
• graph[A].append((B, 1))로 (도착지, 비용) 형태로 저장.
• 다익스트라로 모든 도시까지의 최단 거리 계산 후, 거리 K만 필터링하여 출력.
• found 변수로 거리 K 도시가 없는 경우 -1 출력.

---

📊 플로우차트

단계	플로우	주요 코드	변수 상태 (입력값: 4 4 2 1 / 간선: 1→2, 1→3, 2→3, 2→4)
1	문제 입력 및 초기화	N, M, K, X 입력, graph 초기화	N=4, M=4, K=2, X=1 graph=[[], [], [], [], []]
2	그래프 구성	graph[A].append((B, 1))	graph=[[], [(2,1), (3,1)], [(3,1), (4,1)], [], []]
3	distance 배열 무한대로 초기화	distance = [INF] * (N+1)	distance = [INF, INF, INF, INF, INF]
4	시작 노드 X를 큐에 삽입	heapq.heappush(q, (0, X))	q = [(0,1)] distance[1]=0
5	큐에서 노드 꺼내기	dist, now = heapq.heappop(q)	now=1, dist=0 q=[]
6	인접 노드 탐색	for i in graph[now]:	i = (2,1), (3,1)
7	거리 갱신 및 큐 삽입	distance[i[0]] = dist + i[1] heapq.heappush(q)	distance=[INF, 0, 1, 1, INF] q=[(1,2), (1,3)]
8	다음 pop 및 인접 노드 탐색	pop(1,2) 후 graph[2] 탐색	i = (3,1), (4,1) distance[4] = 2
9	최종 거리 배열 완성	큐 반복 종료	distance=[INF, 0, 1, 1, 2]
10	거리 K 노드 필터링	if distance[i] == 2	출력값: 4