[BOJ 18352] 특정거리의 도시 찾기

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

문제 접근

최종 목표 : 최단거리가 K인 도시를 출력

어떻게 하면 문제를 해결할 수 있을까....? 🤔
일단 문제를 쪼개서 쉬운 문제 여러 개로 바꾸어보자

문제 쪼개기

1. 시작 노드(S)에서부터 다음 노드(N)의 최단 거리를 계산 후 다음 노드로 이동
2. 현재 노드(C)와 다음 노드(N)의 최단 거리를 계산 후 다음 노드로 이동
3. 2번을 반복하여 시작 노드(S)와 최단거리가 K인 도시들을 출력

일단 이렇게 해서 전체 문제를 부분 문제 여러 개로 쪼개서 생각해보았다.

이 문제를 확인해보면 모든 엣지의 길이가 1이라는 점이 문제 해결의 키포인트로 보인다.

문제 해결 아이디어

D(시작 노드, 현재 노드) = D(시작 노드, 이전 노드) + 1이다.

이를 이용하면 BFS로 간단하게 해결할 수 있다.

코드

from collections import deque

# 도시의 개수(N), 도로의 개수(M), 거리 정보(K), 출발 도시번호(X)
n, m, k, x = map(int, input().split())

# 인접 리스트 입력
graph = [[] for i in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)

# 최단거리 리스트(start 노드에서 부터 해당 노드 까지의)
dist = [-1] * (n+1)

def bfs(graph, dist, target, start):
    # 시작 노드 큐에 삽입
    queue = deque([start])
    # 시작노드 최단거리 초기화
    dist[start] = 0

    while queue:
        current = queue.popleft()
        # 인접 리스트를 탐색
        for next_node in graph[current]:
            # 방문하지 않은경우
            if dist[next_node] == -1:
                # 최단거리 갱신
                dist[next_node] = dist[current] + 1
                queue.append(next_node)

    # 최단 거리가 정확히 K인 도시 출력
    if target in dist:
        for i in range(1, n+1):
            if target == dist[i]:
                print(i)
    # 없을 경우 -1 출력
    else:
        print(-1) 
    
    return

bfs(graph, dist, k, x)