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

Breadth First Search

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

문제

구조화

• 노드의 개수 n, edge의 개수 m, 노드 간 거리 k, start node x
• 주어진 그래프에서 start node에서 k만큼 이동할 수 있는 노드를 모두 출력하는 문제
• 만약, k만큼 갈수 있는 경우가 없다면 -1을 출력
• 단, 단방향 그래프이기에 양방향 그래프로 구현할 경우 왕복의라는 case가 존재
• start node에서 한 방향으로 k만큼 갈 수 있는 모든 node를 저장한 뒤 오름차순으로 출력

예제 시각화

해답

from collections import deque
import sys
input = sys.stdin.readline
n,m,k,x = map(int, input().split())
graph = [[] for i in range(n+1)]
state = [-1 for j in range(n+1)]
for i in range(m):
    a,b = map(int, input().split()) # 단방향 그래프 구현을 위해 한 노드에서만 갈 수 있도록
    graph[a].append(b)

for j in range(len(graph)):
    graph[j] = sorted(graph[j]) # 정렬 
    
def bfs(node):
    ans = []
    a=deque([node])
    state[node] = 1 # 스타트를 1로, count로 올리면 순서가 되어버리므로, 현재 노드의 거리를 다음 노드의 +1씩 더해주며 depth 계산
    while len(a):
        node = a.popleft()
        for nxt in graph[node]:
            if state[nxt]==-1:
                a.append(nxt)
                state[nxt]=state[node]+1
                if state[nxt]-1==k: # start를 1로 잡았으므로, -1한 값이 최단거리와 동일한 경우
                    ans.append(nxt) # 정답 리스트에 추가하기
            else:
                continue
    return ans
ans = bfs(x)
ans = sorted(ans) # 오름차순
if len(ans)==0: # return 값이 없다면 -1
    print(-1)
else:
    for i in ans: # 있다면 출력
        print(i)