18352: 특정 거리의 도시 찾기

문제 링크

18352: 특정 거리의 도시 찾기

구현 방식

• dijkstra로도 풀 수 있고, bfs로도 풀 수 있다

코드

• dijkstra 풀이

import sys
import heapq

N, M, K, X = map(int, sys.stdin.readline()[:-1].split())
graph = dict()
for m in range(M):
    A, B = map(int, sys.stdin.readline()[:-1].split())
    if A in graph: graph[A].append(B)
    else: graph[A] = [B]

def dijkstra(start):
    global distances
    distances[start] = 0

    heap = []
    heapq.heappush(heap, [distances[start], start])

    while heap:
        curr_distance, curr = heapq.heappop(heap)
        if distances[curr] < curr_distance: continue

        if curr in graph:
            for next in graph[curr]:
                next_distance = curr_distance + 1
                if next_distance < distances[next]:
                    distances[next] = next_distance
                    heapq.heappush(heap, [next_distance, next])

distances = dict()
for i in range(1, N+1): distances[i] = int(10e9)

dijkstra(X)

answer = []
for key, value in distances.items():
    if value == K: answer.append(key)
answer.sort()
if not answer: print(-1)
else:
    for a in answer:
        print(a)

• bfs 풀이

import sys
from collections import deque

N, M, K, X = map(int, sys.stdin.readline()[:-1].split())
graph = dict()
for m in range(M):
    A, B = map(int, sys.stdin.readline()[:-1].split())
    if A in graph: graph[A].append(B)
    else: graph[A] = [B]

def bfs(start):
    global flag
    queue = deque([]); queue.append((start, 0))
    visit = set(); visit.add(start)

    while queue:
        curr, cnt = queue.popleft()
        if cnt == K: answer.append(curr)
        
        if curr in graph:
            for next in graph[curr]:
                if next not in visit:
                    visit.add(next)
                    queue.append((next, cnt+1))

answer = []
bfs(X)
if not answer: print(-1)
else:
    answer.sort()
    for a in answer: print(a)