18352번 특정 거리의 도시 찾기

문제

특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/18352

풀이

전형적인 BFS 문제이다.
단방향 도로이기 때문에 city[a].append(b) 한 줄만 써준다.
만약 양방향이라면 city[b].append(a) 반대쪽도 추가해줘야 한다.

d라는 거리 리스트에 각 거리들을 저장한다.

d[i] = d[node] + 1

• 이미 방문한 곳의 거리에 1를 더한 값을 현재 방문한 곳에 할당한다.

# -1로 방문 리스트 생성
visited = [-1] * (n+1)
# 처음 방문 하는 곳은 0
visited[start] = 0
# 만약 방문하지 않았다면
if visited[i] == -1:
	visited[i] = visited[node] + 1

• 거리 리스트를 따로 만들지 않고 방문 리스트에 한꺼번에 처리해도 된다.
  

전체 코드

import sys
from collections import deque
input = sys.stdin.readline

n, m, k, x = map(int, input().split())
city = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    city[a].append(b)
    
visited = [0] * (n+1)
d = [0] * (n+1)
result = []

def bfs(start):
    queue = deque([start])
    visited[start] = 1
    while queue:
        node = queue.popleft()
        for i in city[node]:
            if not visited[i]:
                queue.append(i)
                visited[i] = 1
                d[i] = d[node] + 1
                if d[i] == k:
                    result.append(i)
    if result:
        result.sort()
        print(*result,sep='\n')
    else:
        print(-1)

bfs(x)

참고

BFS 알고리즘 개념 설명