[백준]1697번 숨바꼭질 (Python/파이썬)

1. 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다.

 

만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

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

 

💡 수빈이의 노드 N에서 동생 노드 K까지의 최단 경로(시간)를 묻는 문제입니다.

💡 두 노드 간의 최단 경로 문제에서는 BFS(너비우선탐색)를 사용하는 게 익숙해서 저는 BFS로 구현했습니다!

---

2. 입/출력

1) 입력

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

 

💡 0부터 100,000까지의 양의 정수로 수빈이와 동생의 노드 값이 입력됩니다.

 

2) 출력

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

 

3) 예제

> 주어진 예제

# Input
5 17

# Output : 4

 

+) 힌트

위의 주어진 예제 입력에서 4가 나온 이유는, 수빈이가 5-10-9-18-17 순으로 이동하면 4초만에 동생을 만날 수 있기 때문입니다.

 

이 힌트를 통해 수빈이가 이동 가능한 위치는 5부터 17까지로 한정되는 게 아니라,

0부터 100,000까지의 정수 범위 내에서 동생 위치를 넘어서도 이동 가능하다는 것을 알 수 있습니다.

 

> 추가 예제

문제 설명에 나와 있지 않지만, 아래와 같은 경우를 고려해서 출력 값을 지정해야 맞출 수 있습니다. 

• 수빈이와 동생의 위치가 동일한 경우(N==K), 0을 출력합니다.
• 수빈이가 동생의 위치까지 이동할 수 없는 경우(BFS 탐색 불가), -1을 출력합니다.

---

3. 구현 코드

수빈이가 이동할 수 있는 경우는 앞으로(+1), 뒤로(-1), 순간이동(×2)입니다.

현재 노드의 이동 가능 경우를 고려하여 BFS를 구현하였습니다.

from collections import deque

def bfs(graph):
    need_search = deque([N])

    a = [1, 1, 2]
    dx = [1, -1, 0]

    while need_search:
        x = need_search.popleft()

        for i in range(3):
            nx = a[i] * x + dx[i]

            if nx == K:
                print(graph[x])
                exit()

            if (0 <= nx < max_thresh) and graph[nx] == 0:
                need_search.append(nx)
                graph[nx] = graph[x] + 1


### Main ###
N, K = map(int, input().split())
max_thresh = 100001

graph = [0 for _ in range(max_thresh)]
graph[N] = 1
graph[K] = -1

if N == K:
    print(0)
    exit()

bfs(graph)
print(-1)

 

이 문제와 유사하게 노드가 이동하는 경우에 따라 탐색을 하여 최단 경로/시간을 구한 다른 문제의 코드입니다.

2024.04.11 - [코딩테스트] - [백준]2178번 미로탐색 (Python/파이썬) - BFS 코테 문제

[백준]2178번 미로탐색 (Python/파이썬) - BFS 코테 문제

---

 

1차원 배열에서의 탐색을 수행하기 때문에 비교적 쉬운 문제였습니다.

문제를 풀수록 알고리즘을 설계하는 것만큼 반례를 찾는 게 중요한 것 같아요..😢

문제에 나와 있지 않는 반례를 처음 생각하기 어렵다면, 백준의 게시판을 활용하는 것도 좋은 것 같습니다.

 

아무튼, 이번 문제는 쉬운 편이어서 처음으로 다른 분의 코드를 참고하지 않고 풀었네요ㅎㅎ

기분이 좋습니다😊

---

문제 출처

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

1697번: 숨바꼭질