[백준_Python] 13549번 숨바꼭질 3 [골드 5]

황준성·2024년 12월 16일

DFS/BFS 백준

BOJ_Python

목록 보기

40/70

2024.12.20 다익스트라 알고리즘을 이용한 풀이를 추가

문제

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

입력 예시 1

5 17

출력 예시 1

문제 이해

숨바꼭질 1번 문제와 비슷한데 주의할 점이 있다. 먼저 순간이동을 하는 경우에는 시간이 들지 않는다. 그래서 이동 방식 중 가장 먼저 시도해야할 것은 x2이다. 지금처럼 간선의 길이가 다양한 경우에 BFS를 실행하면 처음 도달한 값이 최단거리가 아닐 수 있다. 또 주의해야 할 점은 만약 탐색 순서가 x2, x+1, x-1면 오답이 된다. 우선순위에 따라서 배치할 필요가 있다. 우선순위는 시간이 안들고 거리가 가장 먼 x*2, 그리고 x-1, 마지막이 x+1이다.

그 이유는 4에서 6으로 가는 경우

오답 순서: 2 (4->5->6)
정답 순서: 1 (4->3->6)

참고:
https://www.acmicpc.net/board/view/127319

BFS 코드

# 백준 13549번 숨바꼭질 3

# 읽기 속도 효율화
import sys
input = sys.stdin.readline

from collections import deque

# function BFS
def BFS(x, times):
    global visited

    queue = deque()
    queue.append((x, times))

    while queue:
        x, times = queue.popleft()

        if x == K:
            print(times)
            return
        
        # 이동 방식을 두는 순서도 중요함
        for nx in [x*2, x-1, x+1]:
            if 0 <= nx <= MAX and not visited[nx]:
                if nx == (x*2):
                    visited[nx] = 1
                    queue.append((nx, times))
                else:
                    visited[nx] = 1
                    queue.append((nx, times+1))

# 0. 입력 및 초기화
N, K = map(int, input().split())

MAX = 100000
visited = [0] * (MAX+1)

# 1. BFS호출 및 출력
BFS(N, 0)

Dijkstra code

# 백준 13549번 숨바꼭질 3

# 읽는 속도 효율화
import sys
input = sys.stdin.readline

# Import PriorityQueue
from queue import PriorityQueue

# 0. 입력 및 초기화
MAX = 100000
INF = int(1e12)

N, K = map(int, input().split())
graph = [0]
time = [INF] * (MAX + 1)

# 1. Excute Dijkstra Algorithm

pq = PriorityQueue()
pq.put([0, N]) # cur_time, start_node
time[N] = 0 # 시작점 거리값은 0

while not pq.empty():

    cur_time, cur_node = pq.get()

    nexts = [
        [cur_time, cur_node*2],
        [cur_time+1, cur_node+1],
        [cur_time+1, cur_node-1]
    ]
    for next_time, next_node in nexts:
        if 0 <= next_node <= MAX:
            if next_time < time[next_node]:
                time[next_node] = next_time
                pq.put([next_time, next_node])

# 2. Print result
print(time[K])

다익스트라 알고리즘을 배우기 시작하고 세번째로 푼 문제이다. 보통 다익스트라는 adj_list를 이용하는데 이번 문제는 next step이 정해져 있기 때문에 인접리스트는 필요하지 않다. 아직 다익스트라를 배운지 얼마 안되어서 그런지 인접 리스트 없이 새로운 방식으로 적용하는게 좀 어렵다. 헷갈리는 부분도 있고.. 계속 공부하면서 다른 문제도 풀고, 풀었던 문제도 풀면서 개념을 더 익혀야겠다.

헷갈리는 이유는 원래는 distance리스트를 쓰는데 이 문제에서는 time으로 쓰는게 더 알맞는 것 같음. 그래서 더 헷갈리는 것 같다. distance -> time, node -> position 같은 것들.

1차 수정 및 구구절절 삭제

# 백준 숨바꼭질 3 연습

import sys
input = sys.stdin.readline

from queue import PriorityQueue

INF = int(1e12)
MAX = int(1e5)

N, K = map(int, input().split())
time = [INF] * (MAX+1)

pq = PriorityQueue()
pq.put([0, N]) # cur_time, start_node or position
time[N] = 0 # 시작점은 거리 0

while not pq.empty():

    cur_time, cur_position = pq.get()

    nexts = [
        [cur_time, cur_position * 2],
        [cur_time + 1, cur_position + 1],
        [cur_time + 1, cur_position - 1]
    ]

    for next_time, next_position in nexts:
        if 0 <= next_position <= MAX:
            if next_time < time[next_position]:
                time[next_position] = next_time
                pq.put([next_time, next_position])

print(time[K])