[python] 백준 18352 : 특정 거리의 도시 찾기(BFS)

[python] 백준 18352 : 특정 거리의 도시 찾기

18352번: 특정 거리의 도시 찾기 (acmicpc.net)

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

실버 2

그래프, BFS

---

접근

단방향 그래프 구현과 특정 정점으로부터의 거리를 구현할 수 있으면 쉽게 풀 수 있는 문제이다.

 

코드

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

def bfs(node):
    queue = deque([[node, 0]])
    visited[node] = True
    ans = []
    while queue:
        a, b = queue.popleft()  # b에는 node로부터의 거리가 누적된 값이 할당된다.
        if b > reach:  # 설정한 거리보다 값이 커진 경우 더 계산하지 않고 넘긴다.
            continue
        for i in graph[a]:
            if not visited[i]:
                visited[i] = True
                if b+1 == reach:
                    ans.append(i)
                queue.append([i, b+1])
    
    if len(ans) == 0:
        print(-1)
    else:
        ans.sort()  # 오름차순으로 출력
        for a in ans:
            print(a)
    
    
city_num, road_num, reach, start_node = map(int, input().split())
visited = [False] * (city_num + 1)
graph = [[] for _ in range(city_num+1)]
for i in range(road_num):
    x, y = map(int, input().split())
    graph[x].append(y) # 단방향으로 설정

bfs(start_node)