[백준] 숨바꼭질

문제

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

TC

방문 처리를해서, 한 번 방문한 곳은 방문하지 않고, deque의 push, pop 연산의 시간 복잡도는 O(1)으로, 알고리즘의 시간 복잡도는 O(n)이다.

Idea

매 순간 선택지는 x-1, x+1, x * 2가 있다. 동생이 있는 위치까지 최소 시간에 가는 것을 목적으로 하기 때문에 최단거리 문제라고 생각했다. 그래서 BFS로 구현하였다.

방문해야 하는 지점의 수가 최대 100,000으로 2초 시간 제한을 통과하려면 O(n)이내의 시간 복잡도로 연산을 수행해야 한다.

code (Python)

from collections import deque

def bfs():
    queue = deque()
    queue.append(n)

    while queue:
        x = queue.popleft()
        # 현재 위치가 동생이 있는 위치라면
        if x == k:
            print(time[x])
            break
        # 현재 위치 x로부터 이동 가능한 위치는 x-1, x+1, x*2
        for i in (x-1, x+1, x*2):
            # 범위 내이고 방문했던 칸이 아니라면
            if 0 <= i <= 100000 and not time[i]:
                # 현재 위치 + 1 시간이 새로운 위치 i까지의 도달 시간
                time[i] = time[x] + 1
                queue.append(i)

# n=수빈이 위치, k=동생 위치
n, k = map(int, input().split())
# 점의 최대 위치는 100,000
time = [0] * 100001
bfs()

self code review

처음에는 x-1, x+1, x * 2만 보고 DP인줄 알았다.
그래서 점화식을 세우려고 해봤는데, 규칙을 찾을 수가 없었다...ㅎㅎ
문제를 다시 꼼꼼히 읽어보니 최단거리를 구하는 문제임을 알 수 있었고,
BFS 방식을 떠올라서 다시 풀어보니 맞았다!