해결 과정
BFS를 어떻게 활용해야 할지 감이 안왔다. 최단경로를 찾는 문제.
dis = [-1, -1, -1, ... -1] (총 노드의 개수만큼) 를 가지고 있고, BFS를 활용하며 dis가 여전히 -1인 상태일때만 update 해준다.
다익스트라 알고리즘을 사용한 사람들도 많았는데(우선순위 큐 사용), 살펴보자. 참고로 내가 제출한 코드는 pypy로 제출해야만 시간초과가 안났다.
나의 풀이
from collections import deque
N, M, K, X = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b)
# 최단거리 구하기
dis = [-1] * (N+1)
dis[X] = 0
queue = deque([X]) # 첫번째 원소 집어넣은 상태
while queue:
cur = queue.popleft()
for i in graph[cur]: # cur에 연결되어 있는 도시
if dis[i] == -1:
dis[i] = dis[cur] + 1
queue.append(i)
# candidates = []
flag = False
for idx, value in enumerate(dis):
if value == K:
print(idx)
flag = True
# candidates.append(idx)
if flag == False:
print(-1)
다른 풀이
import heapq
import sys
read = sys.stdin.readline
def solve():
N, M, K, X = map(int, read().split())
# 인접 리스트
adj = [list() for _ in range(N+1)]
for _ in range(M):
f, t = map(int, read().split())
adj[f].append(t)
# 최단 거리 배열
min_dists = [300002] * (N+1)
# 우선순위 큐
# (해당 노드까지의 최단거리, 노드번호) 튜플을 원소로 가짐
q = []
heapq.heappush(q, (0, X))
min_dists[X] = 0
ans = []
# 남은 모든 노드들에 대하여
while q:
# 우선순위 큐 안에 있는 최단 거리 노드 선택
dist, node = heapq.heappop(q)
# 이미 처리된 노드라면 continue
if min_dists[node] < dist:
continue
# 현재 노드까지의 거리가 K라면 정답 리스트에 저장 후 continue
if min_dists[node] == K:
ans.append(str(node))
continue
# 연결된 노드들의 최단거리 갱신 후 우선순위 큐에 추가
for to in adj[node]:
if min_dists[to] > dist + 1:
min_dists[to] = dist + 1
heapq.heappush(q, (dist+1, to))
return '\n'.join(ans) if ans else -1
print(solve())
IDEA
다익스트라 알고리즘
https://techblog-history-younghunjo1.tistory.com/248?category=1014800
'Coding Test > 문제 풀이' 카테고리의 다른 글
[문제 풀이] 백준 10825 (0) | 2022.03.25 |
---|---|
[문제 풀이] 백준 1446 (0) | 2022.03.25 |
[문제 풀이] 무지의 먹방 라이브 (0) | 2022.03.24 |
[문제 풀이] 백준 1439 (0) | 2022.03.24 |
[문제 풀이] 백준 1644 (0) | 2022.03.23 |