[Python] 백준 #18352 - 특정 거리의 도시 찾기

문제

---

 

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

코드

---

My answer

import heapq
import sys
input = sys.stdin.readline
INF = int(1E9)

N, M, K, X = map(int, input().split())

graph = [[] for _ in range(N+1)]
distance = [INF for _ in range(N+1)]
answer = 0

for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))  
    distance[start] = 0 

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


dijkstra(X)

for i in range(1, N+1):
    if (distance[i] == K):
        print(i)
        answer += 1
# print(distance)
if (answer == 0):
    print(-1)

Another answer

from collections import deque
import sys
f = sys.stdin.readline

n, m, k, x = map(int, f().split())
graph = [[] for _ in range(n+1)]
distance = [0] * (n+1)
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, f().split())
    graph[a].append(b)

def bfs(start):
    answer = []
    q = deque([start])
    visited[start] = True
    distance[start] = 0
    while q:
        now = q.popleft()
        for i in graph[now]:
            if not visited[i]:
                visited[i] = True
                q.append(i)
                distance[i] = distance[now] + 1
                if distance[i] == k:
                    answer.append(i)
    if len(answer) == 0:
        print(-1)
    else:
        answer.sort()
        for i in answer:
            print(i, end='\n')

bfs(x)

풀이

---

우선 나는 다익스트라 최단거리를 공부하면서 풀었기 때문에 해당 알고리즘으로 해결하였다.

기본적인 heap 우선순위큐를 활용한 다익스트라 최단거리 알고리즘에서 초기 거리만  1로 고정하여 풀면 되는 문제였다.

추후에 다익스트라 알고리즘에 대한  글을 올리면서 설명하도록 하겠다.

another answer은 bfs로 해결하였는데, 다익스트라랑 거의 비슷한 문제로 다만, visited라는 방문을 기록하는 리스트를 따로 선언하여 해결하였다.