[BFS, Dijkstra] 백준 18352번 '특정 거리의 도시 찾기' (Python)

<문제 링크>

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

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

---

이 문제는 BFS 또는 다익스트라 알고리즘으로 풀 수 있다.

BFS로 푸는 법은 다음에 기록할 예정이다.

 

<문제풀이>

1. 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하므로 다익스트라 알고리즘 사용
2. M 개수가 1,000,000 이하이므로 input() 보다 빠른 sys.stdin.readline 라이브러리 사용
3. 비용을 구하는 것이 아닌 특정 노드를 구하는 것

<코드>

'''입력예시
4 4 2 1
1 2
1 3
2 3
2 4

4 3 2 1
1 2
1 3
1 4

4 4 1 1
1 2
1 3
2 3
2 4
'''

import heapq
import sys

input = sys.stdin.readline
n,m,k,x = map(int,input().split())

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

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 = dist+i[1]
            if cost<distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost,i[0]))

dijkstra(x)

result = []
for i in range(1,n+1):
    if distance[i]==k:
        result.append(i)

if result:
    for i in result:
        print(i)
else:
    print(-1)

#220323
from collections import deque

n,m,k,x = map(int,input().split())

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

count = [0 for i in range(n+1)]
visited = [False for i in range(n+1)]
answer = []
q = deque([x])
visited[x] = True

while q:
    v = q.popleft()
    for i in graph[v]:
        if visited[i] == False:
            visited[i] = True
            q.append(i)
            count[i] = count[v]+1
    if count[v]==k:
        answer.append(v)

if answer==[]:
	print(-1)
else:
	for i in sorted(answer):
		print(i)

 

<고쳐야 할 점>

1. for i in graph[now] 반복 학습