[BOJ] 1697. 숨바꼭질

문제

숨바꼭질 (https://www.acmicpc.net/problem/1697)

풀이

1. 초기 접근

• 문제조건 해석
  • 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다.
    • BFS 문제다.
• 알고리즘
  • 이동 방향이 3가지로 정해져 있다.
  • 목표지점이 정해져있으므로, 해당 목표지점에 도달 시, BFS를 끝내고, 지금까지 간선의 스텝(time) 을 반환한다.
  • 우리는 모든 노드를 최대한 1번 방문하며 BFS를 진행한다. 따라서 시간 복잡도는 O(n) 이다.
    • 맨 처음 생각엔, 한 스텝에서 갈 수 있는 경우의수가 3가지 이므로, n번 스텝까지 진행할 시, O(3^n) 이 아닌가 했다. 이는 매우 큰 수로, k가 좀만 커져도 1억을 넘어 시간초과다.
    • BFS의 시간복잡도는 O(|V|+|E|) 로 알려져있다. 여기에서는, 노드들이 그려져있고 (100,000개) BFS 탐색을 하며 간선을 그려나가는 식이다.
      그런데 탐색 중에 한 번 방문한 노드는 재방문 하지않는다. 왜냐하면 재방문 할 때의 스텝(time) 이 당연히 맨 처음 방문할 때보다 더 크기 때문이다. 우리는 '최소 스텝' 의 경로를 찾고있다.
    • 따라서, 최대 간선의 수는 노드의 수를 넘지 않는다. 즉, |V| >= |E| 다.
    • 따라서, 시간 복잡도도 O(|V|), 즉 O(n) 이라고 볼 수 있는 것이다.
    • 맨 처음 O(3^n) 이 도출된 것은, '재방문 하지 않음' 을 고려하지 않은 시간복잡도라고 할 수 있겠다.
• 코드

import sys

n, k = list(map(int, sys.stdin.readline().split()))

def bfs(n):
    q, visited = [n], {n}
    time = 0
    while q:
        size = len(q)

        for i in range(size):
            cur = q.pop(0)
            if cur == k:
                return time

            next_move = [cur-1, cur+1, cur*2]

            for j in next_move:
                if j >= 0 and j <= 100000 and j not in visited:
                    q.append(j)
                    visited.add(j)
        time += 1

print(bfs(n))