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

---

ALGORITHM Übung - 백준

• 알고리즘 문제 풀이를 통한 코딩 테스트 연습

---

문제

• 🔗 문제 링크

코드

BFS

import sys
from collections import deque

# bfs, all next node gets +1 from the value of the current node 
def bfs(X):
    visited[X] = True
    distances[X] = 0
    dq = deque([X])

    res = []
    while dq:
        now = dq.popleft()
        for i in graph[now]:
            if not visited[i]:
                dq.append(i)
                visited[i] = True
                distances[i] = distances[now] + 1
                if distances[i] == K:
                    res.append(i)
    return res


if __name__ == "__main__":
    N, M, K, X = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N+1)]

    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)

    visited = [False] * (N+1)
    distances = [0] * (N+1)
    res = bfs(X)
    
    if not res:
        print(-1)
    else:
        res.sort()
        for i in res:
            print(i)

Djikstra

import sys
import heapq


def djikstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distances[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
        
        if distances[now] < dist: 
            continue
        
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distances[i[0]]:
                distances[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


if __name__ == "__main__":
    N, M, K, X = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N+1)]

    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append((b,1))

    distances = [float("inf")] * (N+1)
    
    djikstra(X)
    
    equals_K = False
    for i in range(len(distances)):
        if distances[i] == K:
            print(i)
            equals_K = True
    
    if not equals_K:
        print(-1)