백준: 1697 숨바꼭질

숨바꼭질 시리즈

• 숨바꼭질
• 숨바꼭질 2
• 숨바꼭질 3
• 숨바꼭질 4

 

문제

1697번: 숨바꼭질

 

문제 풀이

 수빈이의 위치와 동생의 위치가 주어질 때 가장 빠른 시간에 동생을 찾는 것은 몇 초 후인지 구하는 문제이다. 동생을 찾기 위해 이동 할 수 있는 방법은 1초가 지날 때마다 현재 위치 -1, 현재 위치 + 1, 현재 위치 * 2로 나뉜다. 이와 같은 경우의 수에 따라 예제 입력 1을 찾기 위한 과정을 트리로 나타내면 위의 그림과 같다.

 그림에서도 알 수 있듯이 이 문제를 DFS로 찾게 되면, 무한 루프에 빠질 수 도 있으며 답을 찾는데 효율적이지 않다. 따라서 BFS를 통해 경우의 수를 큐에 추가하는 방식을 사용하여 답을 찾으면 된다. 방문 여부를 확인하는 visited에 걸린 시간을 중첩하여 동생을 찾는데 걸린 시간을 구할 수 있다.

 

코드

from sys import stdin
from collections import deque


def bfs(start):
    q = deque([start])

    while q:
        cur_loc = q.popleft()
        if cur_loc == k:
            return visited[cur_loc]

        for next_loc in (cur_loc - 1, cur_loc + 1, cur_loc * 2):
            if 0 <= next_loc < MAX_LOC and not visited[next_loc]:
                visited[next_loc] = visited[cur_loc] + 1
                q.append(next_loc)

if __name__ == '__main__':
    MAX_LOC = 100001
    n, k = map(int, stdin.readline().split())
    visited = [0] * MAX_LOC
    print(bfs(n))

 위의 그림 처럼 경우의 수에 따라 가지를 뻣기 위해, 반복문을 통해 현재 지점 - 1, +1, *2의 방문 가능 여부에 따라, 큐에 추가한다. 현재 위치가 동생의 위치 (k)와 같아진다면 더 이상 진행하지 않고 종료한다.