숨바꼭질

문제

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

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

문제를 보고 든 생각

뭔가 풀 수 있을 것 같았다.

움직이는 상황의 경우의 수만 잘 생각해서 코드로 옮길 수 있다면

이 문제를 해결할 수 있을 것 같았다.

나의 아이디어

수빈이가 움직일 수 있는 상황을 4가지로 생각했다.

 

1. 걷기만 하는 경우

2. 순간이동만 하는 경우

3. 걷고 난 후 순간이동을 하는 경우

4. 순간이동을 한 후 걷는 경우

 

코드로 옮기기 전 위의 경우의 수를 이용한 사전 계산에서 예제 문제가 해결되어 코드로 옮겨보았지만

어찌어찌 옮기고 나니 뒤늦게 문제가 발생했다.

 

가는 동안의 거리를 어떻게 계산해야 할지 생각을 못했던 것이다.

결과

결국 코드를 완성시키지 못했다.

검색을 통해 알게 된 내용

상황은 그냥 문제에 제시된 그대로 3가지로 생각해도 됐던 것이었다.

 

1. 뒤로 한 걸음 걷는 상황

2. 앞으로 한 걸음 걷는 상황

3. 순간이동을 한 상황

 

더불어, 이 세 가지 상황을 계산한 값에 적용하는 방법이 되게 어려웠는데 for문에서 3가지 상황을 처리하는 게 가능하다는 걸 배웠다.

 

그리고 나에게 있어서 풀이의 핵심이었던 가는 동안의 거리를 어떻게 계산하는지의 방법에 대해 알 수 있었다.

검색을 통해 알게 된 풀이

from collections import deque

n, k = map(int, input().split())

max_vertex = 10 ** 5
dist = [0] * max_vertex

def hide_and_seek():
    q = deque([n])
    while q:
        now = q.popleft()
    
        if now == k:
            print(dist[now])
            break
        
        # 움직이는 세 가지 상황
        for step in [now - 1, now + 1, now * 2]:
            if 0 <= step <= max_vertex and dist[step] == 0:
                q.append(step)
                dist[step] = dist[now] + 1
hide_and_seek()

과정은 아래와 같다.

 

1. 수빈이의 위치 n, 동생의 위치 k를 입력 받는다.

 

2. max_vertex는 수빈이와 동생이 위치할 수 있는 최대 정점의 위치를 의미한다. 이는 문제에서 알려준 그대로 조건을 적용했다. 그리고 dist는 거리 계산을 위한 리스트이다. 예를 들어 dist[3]은 정점 3까지 가는 데 걸리는 거리(레벨 수)를 의미한다.

 

3. 가장 먼저 bfs를 시작하기 전 q라는 deque에 n의 값을 넣어 초기화해준다.

 

4. while문이 q가 비어있지 않은 동안 돌도록 한다.

 

5. q에 가장 먼저 들어간 요소를 빼서 now라는 변수에 저장한 후 만약 now가 동생이 위치한 정점을 가리킨다면 now까지 가는데 걸리는 거리를 출력하기 위해 dist[now]를 출력해주고 반복문을 종료한다.

 

6. 움직이는 세 가지 상황을 리스트에 넣어서 for문을 돌려주면 계산된 값이 step으로 들어간다. 그 step값이 0 <= step <= max_vertex 라면 그리고 한 번도 방문하지 않았던 정점이라면 q에 step을 추가해준다.

6-1. 그리고 dist[step] = dist[now] + 1은 현재 값인 step까지 가는데 걸리는 거리를 갱신해주는 것인데, dist[now]는 방금까지 온 거리를 의미한다. 여기에 1을 더해주면 현재 도착한 정점인 step의 거리가 저장되는 것이다.

 

느낀 점

이렇게 차근차근 많은 문제와 풀이법을 보다보면 내가 방법을 떠올릴 수 있는 날이 오지 않을까.

잘 모르니까 반복이라도 하자.