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

문제

백준 온라인 저지 - 18352번

풀이 과정

특정 지점에서 목표 지점에 도달하기 위한 최단 거리들 중에서 K 인 정점들을 찾는 문제입니다.

처음에는 단순한 BFS 문제인줄 알고 접근했다가 최단 거리를 구하는 시점 때문에 자꾸 오답이 발생해서 삽질을 하다가

다익스트라 로 다시 접근해서 문제를 해결했습니다.

코드

import sys
from collections import deque

N, M, K, X = list(map(int, sys.stdin.readline().split()))
edges = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]


def make_graph():
    graph = [[] for _ in range(N + 1)]

    for frm, to in edges:
        graph[frm].append(to)

    return graph


def bfs(graph):
    answer, q = [], deque()
    dist = [-1] * (N + 1)

    dist[X] = 0
    for near in graph[X]:
        q.append(near)
        dist[near] = 1

    while q:
        here = q.popleft()

        for there in graph[here]:
            if dist[there] == -1:
                dist[there] = dist[here] + 1
                q.append(there)

    for there in range(1, N + 1):
        if dist[there] == K:
            answer.append(there)

    return answer if answer else [-1]


def solution():
    graph = make_graph()
    answer = bfs(graph)

    print(*answer, sep='\n')


solution()