숨바꼭질 - 백준알고리즘 1697번

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

1697번: 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

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

 

from collections import deque

# 그래프 자체가 0부터 100000번째 까지 존재해야하므로
max_size = 100001
N, K = map(int, input().split())
visited = [0 for _ in range(max_size)]

def bfs(node):
    queue = deque()
    queue.append(node)
    # 노드를 방문하였으므로
    visited[node] = 1

    while queue:
        current = queue.popleft()
        # 인접노드를 설정하자
        d = [current - 1, current + 1, current * 2]
        # 술래를 잡는 다면
        if current == K:
            return visited[current] - 1
        # 인접노드를 돌자
        for i in d:
            next = i
            # 다음 칸이 범위 내에 있고 방문하지 않은 칸이라면
            if (0 <= next < max_size) and (visited[next] == 0):
                # 해당 칸에 현재 시간을 적어놓자
                visited[next] = visited[current] + 1
                queue.append(next)

#
if N > K:
    print(N - K)
elif N == K:
    print(0)
else:
    print(bfs(N))

문제풀이

 

위 문제는 탐색문제이다.

먼저 수빈이가 5번에 있고 동생이 17번칸에 있다면 생각해보자

5번에서 4번 6번 10번 칸의 선택지가 있고 만약 4번에서 선택했다면 또 3번 5번 8번의 선택지, 6번에서 선택했다면

... 10번에서 선택했다면 9번, 11번, 20번의 선택지가 있다. dfs는 재귀이므로 10번 20번 40번... 해서 칸의 제한수인 

10만 칸을 넘게되는 경우가 발생한다.(가장 멀리, 혹은 깊은 곳부터 탐색하는 경우이므로)

따라서 bfs로 가장 가까운 노드부터 탐색을 시작하는 것이 탐색을 빠르게 끝낼 수 있다.

 

그래프가 1차원적이므로 graph와 visited 리스트를 같이 써버리고 각 칸을 방문 할 때마다

현재시간을 적어 놓는다. (조건을 만족하는 칸으로 가서 큐에 넣어버리는 칸이라면 그전에 있던 칸에 + 1을 한다.

즉 그래프의 단계가 곧 현재 시간이다. 따라서 가장 빨리 술래를 잡는 그래프 단계에서 bfs는 끝나게 되고

해당 단계를 출력하면 곧 그것이 답이다.

 

TIP

1. bfs를 이용하여 메모리 초과하는 경우가 없도록

2. 칸이 범위에 있는지 확인 할것.

3. 그래프단계가 곧 시간인 것을 착안할 것.

4. 그래프가 곧 방문체크하는 리스트이다.

5. bfs 사용시 deque를 꼭 사용할 것. (시간복잡도가 pop 할 때O(1))이다.