[백준] 18352번 특정 거리의 도시 찾기 - 파이썬

https://www.acmicpc.net/problem/18352

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

 

풀이

다익스트라 알고리즘 사용

# 18352번 특정 거리의 도시 찾기
import sys
import heapq
INF = sys.maxsize

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]:
            continue
        for v, w in graph[now]:
            cost = dist + w
            if cost < distance[v]:
                distance[v] = cost
                heapq.heappush(q, (cost, v))

def check(n):
    for i, num in enumerate(distance):
        if num == n:
            print(i)
        

n, m, k, x = map(int, input().split())
graph = [[]*(n+1) for _ in range(n+1)]
distance = [INF] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append((b, 1))

dijkstra(x)

cnt = distance.count(k)

if cnt == 0:
    print(-1)
else:
    check(k)

출력결과

 

풀이

BFS 알고리즘 사용

# 18352-2번 특정 거리의 도시 찾기
# BFS사용
import sys
from collections import deque

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

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

def bfs(start):
    ans = []
    q = deque([(start, 0)])
    visited[start] = True
    
    while q:
        x, cost = q.popleft()

        if cost == k:
            ans.append(x)
            continue
        
        for i in graph[x]:
            if not visited[i]:
                visited[i] = True
                q.append((i, cost+1))
    return sorted(ans)

answer = bfs(x)
if answer:
    for i in answer:
        print(i)
else:
    print(-1)

출력결과