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

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

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

from collections import deque
import sys
n, m, k, x = map(int,input().split())
graph = [[] for i in range(n + 1)]
distance = [-1] * (n + 1)
check = False

def bfs(x):
    queue = deque([x])
    distance[x] = 0
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if distance[i] == -1:
                distance[i] = distance[v] + 1
                queue.append(i)
        

for i in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    
bfs(x)
for i in range(1, n + 1):
    if distance[i] == k:
        print(i)
        check = True
    
if not check:
    print(-1)

이 문제에서 모든 도로의 거리는 1로 동일하기 때문에 BFS를 이용하여 최단 거리를 찾을 수 있다.

특정한 도시 x를 시작으로 BFS를 수행하면서 모든 도시까지의 최단 거리를 계산하여 distance 배열에 저장한 후, 각각을 확인하며 그 값이 k인 경우에 해당 도시의 번호를 출력하면 된다.

 

# 도시 연결 정보 저장할 인접 리스트
graph = [[] for i in range(n + 1)]

# 간선 정보 입력 받기
for i in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)

위의 코드는 도시의 연결 정보를 입력받는 부분이다. 비어있는 인접 리스트를 만든 다음에 도시 a, b를 입력받고, 단방향 그래프이기 때문에 graph[a].append(b)를 통해 a에서 갈 수 있는 도시에 b를 추가한다. 만약 양방향이었다면 graph[b].append(a)도 해주어야한다.

 

if distance[i] == -1:
                distance[i] = distance[v] + 1
                queue.append(i)

bfs() 함수에서 위의 코드는 방문한 도시가 처음 방문한 것이라면 이전 도시까지의 최단거리 + 1로 그 도시의 최단거리를 저장하는 부분이다. 그 후 그 도시를 큐에 추가하여 연결된 다음 도시를 방문할 수 있게 해준다.