Light theme icon (depiction of a sun)
Dark theme icon (depiction of a moon)

[이.취.코] [백준] Chap 13. BFS - Q15. 특정 거리의 도시 찾기

  • 0
  • 0
0
0

1. 특정 거리의 도시 찾기

A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 내 답안

a. BFS

# BFS  
from collections import deque  
import sys  
  
# n, m, k, x = list(map(int, input().split()))  
n, m, k, x = list(map(int, input().split()))  
  
array = [[] for i in range(n+1)]  
count = [k+1] * (n+1)  
  
count[0] = 0  
count[x] = 0  
  
for _ in range(m):  
    a, b = list(map(int ,input().split()))  
    array[a].append(b)  
  
q = deque()  
q.append(x)  
  
while q:  
    src = q.popleft()  
  
    for i in array[src]:  
        if count[i] > count[src] + 1:  
            count[i] = count[src] + 1  
            q.append(i)  
  
if k not in count:  
    print(-1)  
else:  
    for i in range(len(count)):  
        if count[i] == k:  
            print(i)

b. 다익스트라

# 다익스트라  
  
import heapq  
import sys  
  
n, m, k, x = list(map(int, sys.stdin.readline().split()))  
  
graph = [[] for i in range(n+1)]  
distance = [1e9] * (n+1)  
  
for _ in range(m):  
    a, b = list(map(int, sys.stdin.readline().split()))  
  
    graph[a].append((1, b))  
  
q = []  
heapq.heappush(q, (0, x))  
distance[x] = 0  
  
while q:  
    cost, src = heapq.heappop(q)  
  
    if cost > distance[src]:  
        continue  
  
    for i in graph[src]:  
        dest_cost, dest_node = i  
  
        total_cost = dest_cost + cost  
  
        if total_cost < distance[dest_node]:  
            distance[dest_node] = total_cost  
            heapq.heappush(q, (distance[dest_node], dest_node))  
  
if k not in distance:  
    print(-1)  
else:  
    for i in range(len(distance)):  
        if distance[i] == k:  
            print(i)
            
a. 회고

내 풀이

  • 문제를 보자마자 다익스트라가 떠올랐다.
  • 책의 기출문제 파트가 BFS/DFS라서 BFS나 DFS가 가능한지 생각해봤다.

결론

  • 다익스트라 방식으로도 잘 해결하는 것을 보니, 그럭저럭 적응한 것 같다.

C. 문제 해설

이해한 내용을 바탕으로 작성했습니다.

최단 거리를 구하고 최단거리가 K인 도시를 구하는 문제이다.

직관적으로 봤을 때 다익스트라 문제라서 BFS로 생각하는데 시간이 조금 걸린다.

다익스트라는 노드 사이의 시간을 기준으로 정렬하는 우선순위 큐를 사용하지만, 이 문제에서 모든 도시의 시간은 1로 동일하기 때문에 큐를 이용해서 다음 노드와 현재 노드 + 1을 비교해주고 최솟값만 찾으면 된다.

이 문제가 BFS로 풀리는 이유는 노드 사이의 시간을 따로 정렬해줄 필요가 없기 때문이다. (우선순위 큐를 사용하지 않아도 됨)

a. 책 답안

python-for-coding-test/1.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[2] 18352번: 특정 거리의 도시 찾기 (acmicpc.net). Baekjoon. (accessed Sep 21, 2021)

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.