Algorithm - 술래잡기(백준 1697번) 파이썬 구현 (Python)

술래잡기(백준 1697번) 파이썬 구현 (Python)

오늘은 백준의 1697번 문제 술래잡기를 풀어보겠습니다.

문제

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

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

입력

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

출력

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

예제 입/출력

예제입력

5 17

예제출력

4

이 문제는 여러가지 방법으로 풀 수 있지만, 오늘은 BFS(너비 우선 탐색)를 이용해 풀어보려고 합니다.

BFS는 그래프를 탐색하는 방법 중 하나이고, 최단거리 문제에서 종종 사용되곤 합니다.

풀이

from collections import deque


MAX = 100001


def solution(n, k):
    q = deque([n])
    visit = [0] * MAX

    def nextPos(next, cur):
        if 0 <= next and next < MAX:
            if visit[next] == 0 or (visit[cur] + 1 < visit[next]):
                visit[next] = visit[cur] + 1
                q.append(next)

    while q:
        cur = q.popleft()
        if cur == k:
            return visit[cur]
        nextPos(cur - 1, cur)
        nextPos(cur + 1, cur)
        nextPos(cur * 2, cur)


if __name__ == "__main__":
    N, K = map(int, input().split())
    print(solution(N, K))

전체적인 코드는 위와 같습니다.

우선 deque를 이용합니다.

deque는 앞, 뒤 양 방향에서 O(1)로 데이터를 꺼내올 수 있어 queue를 구현할 때 파이썬의 list보다 훨씬 빠릅니다.

기본적인 구조를 설명하면 이렇습니다.

우리는 문제 내에서 n과 k가 100,000이하라는 것을 알 수 있었습니다. 따라서 MAX는 넉넉하게 100,001로 선언해 줍니다.

먼저 solution함수는 수빈이의 위치 n과 동생의 위치 k를 파라미터로 받고, 찾는데 걸리는 가장 빠른 초를 리턴합니다.

solution 함수 안에서 deque를 선언하고, 수빈이의 위치인 n을 넣어줍니다.

또, visit이라는 리스트를 선언하는 데, 매 방문시마다, 그 지점을 방문하는데 걸린 최소시간(초)을 기록할 예정입니다.

다음으로 nextPos라는 함수를 알아봅시다.

def nextPos(next, cur):
    if 0 <= next and next < MAX:
        if visit[next] == 0 or (visit[cur] + 1 < visit[next]):
            visit[next] = visit[cur] + 1
            q.append(next)

nextPos는 다음 위치를 탐색하며 visit의 다음 위치에, 도달하는데 걸린 최소 시간(초)를 기입하고, 해당 다음 위치를 queue에 추가하는 함수입니다.

while문 분석

바로 nextPos 함수를 이해하면 어려우니 while문을 먼저 살펴보겠습니다.

while q:
    cur = q.popleft()
    if cur == k:
        return visit[cur]
    nextPos(cur - 1, cur)
    nextPos(cur + 1, cur)
    nextPos(cur * 2, cur)

deque로 선언된 queue인 q가 빌 때까지 while문은 지속됩니다.

먼저 q에서 가장 왼쪽 아이템을 pop한 후 cur라는 변수에 담습니다.

cur는 현재위치를 의미합니다.

만약 cur과 k가 같다면 탐색을 완료한 것입니다. 우리는 **queue를 이용하고 있고, 선입선출이 전제되어 있기에,

순차적으로 탐색을 하다 가장 먼저 cur == k 인 지점을 발견하면 그 때까지의 소요시간이 최소시간**이게 됩니다.

그렇기에 만약 cur == k라면 바로 cur까지 탐색에 걸린 소요시간인 visit[cur]을 리턴합니다.

아니라면 cur-1, cur+1, cur*2를 각각 nextPos 함수로 탐색합니다.

nextPos 함수

nextPos 함수가 실행되는 조건은 다음과 같습니다.

• next의 값이 0 이상이다: next는 음수가 될 수도 있는데 양수이거나 0일 때에만 탐색을 합니다.
• next가 MAX보다 작다: n과 k 모두 MAX보다 작아 next가 MAX보다 클 수는 없기 때문입니다.
• visit[next] == 0 이거나 visit[cur] + 1 < visit[next]:
  • visit[next] == 0: 이 경우엔 첫 방문입니다. 탐색 안된 곳이니 탐색을 합니다.
  • visit[cur] + 1 < visit[next] : visit[next]에 있는 값이 visit[cur] + 1보다 크다면, visit[next]에 더 빠르게 도착할 수 있는 방법을 찾은 것입니다. 현재위치인 cur에서 next로 가는 것이 빠르므로 현재위치에서 바로 이동할 때 걸리는 1초를 더하여 visit[cur] + 1 을 넣어주는 것입니다.

이 조건들을 만족하면 다음이 실행됩니다:

visit[next] = visit[cur] + 1
q.append(next)

먼저 visit 리스트의 next 위치에 현재위치에서 이동하는 데 걸리는 시간인 1초를 현재위치까지 오는데 걸린 시간(visit[cur]과 같음)을 더하여 넣어줍니다.

말했다시피, visit[cur]에는 현재위치인 cur까지 오는데 걸린 시간(초)가 들어 있습니다.

cur에서 next로는 이동 가능하고, 1초 만에 이동하기 때문에 현재위치(cur)까지 오는데 걸린 시간에 +1을 한 후, visit[next]에 대입하는 것입니다.

마지막으로 탐색한 지점도 새로운 출발점으로 추가해줘야 하므로 q에 추가해 줍니다.

우리는 각 지점에서 탐색할 수 있는 모든 지점들을 탐색하고 있습니다. 매 지점마다 +1, -1, *2 지점을 탐색할 수 있으므로, 이 지점들을 q에 넣어주고, 계속 탐색을 해 나가는 것입니다.

결론

이렇게 deque와 BFS를 응용하여 최단거리를 찾아내는 문제를 풀어볼 수 있었습니다.