[백준] 1697 번 숨바꼭질

문제

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

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

입력

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

출력

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

예제 입력 1

5 17

예제 출력 1

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

내 코드

def bfs(N, K):
    visited = [False] * 100001
    queue = [(N, 0)]

    while queue:
        next_N, during_sec = queue.pop(0)

        if next_N < 0 or next_N > 100000:
            continue

        # N과 K가 같은 위치면
        if next_N == K:
            return during_sec

        if not visited[next_N]:
            visited[next_N] = True

            # 아니면 1초 증가
            during_sec += 1

            # queue에 넣기
            queue.append((next_N + 1, during_sec))
            queue.append((next_N - 1, during_sec))
            queue.append((next_N * 2, during_sec))

N, K = map(int, input().split(' '))

meet_sec = bfs(N, K)

print(meet_sec)

chatGPT

코드가 BFS를 사용해 잘 구현되어 있지만, 몇 가지 성능 및 코드 개선 사항을 적용해 볼 수 있습니다. 주로 큐 연산 최적화와 불필요한 중복 계산을 제거하는 방법이 있습니다.

개선 사항

1. deque 사용: 현재 queue.pop(0)을 사용해 큐의 첫 번째 요소를 제거하고 있는데, 이는 리스트의 첫 요소 제거 시 O(N) 복잡도를 가지므로 비효율적입니다. collections.deque를 사용하여 O(1) 복잡도로 popleft()를 사용하면 성능이 개선됩니다.
2. during_sec 관리: during_sec를 큐에 넣을 때마다 증가하고 있는데, 중복되므로 불필요합니다. during_sec를 직접 증가시키지 않고, 이동할 때마다 필요한 시간을 함께 저장하면 좋습니다.
3. 이미 방문한 위치 확인 후 큐에 추가: visited 체크는 큐에 넣기 전에 수행하는 것이 좋습니다. 현재 코드는 큐에서 꺼낸 후 visited를 확인하므로, 방문하지 않은 노드만 큐에 추가하도록 개선하면 더 효율적입니다.
4. 문제의 특성에 맞게 순간이동을 우선 탐색: 2 * X로 가는 순간이동은 더 빠르게 위치를 줄일 수 있으므로 BFS에서 우선적으로 탐색하는 것이 좋습니다. 이를 통해 탐색을 조금 더 빠르게 할 수 있습니다.

개선된 코드

위의 개선 사항을 반영한 코드는 다음과 같습니다.

from collections import deque

def bfs(N, K):
    visited = [False] * 100001
    queue = deque([(N, 0)])

    while queue:
        current, time = queue.popleft()

        # K 위치에 도달하면 시간을 반환
        if current == K:
            return time

        # 방문 처리
        if not visited[current]:
            visited[current] = True

            # 순간이동을 우선적으로 추가
            if current * 2 <= 100000 and not visited[current * 2]:
                queue.append((current * 2, time + 1))
            if current + 1 <= 100000 and not visited[current + 1]:
                queue.append((current + 1, time + 1))
            if current - 1 >= 0 and not visited[current - 1]:
                queue.append((current - 1, time + 1))

N, K = map(int, input().split())
print(bfs(N, K))

설명

1. *deque*를 사용해 큐의 popleft() 연산을 효율적으로 수행했습니다.
2. during_sec를 직접 증가시키지 않고, 이동할 때마다 시간을 함께 큐에 추가하여 필요 시만 업데이트했습니다.
3. visited 확인을 큐에 넣기 전에 수행하여 불필요한 중복 계산을 줄였습니다.
4. 순간이동을 우선적으로 탐색함으로써 더 빠르게 목표 위치에 도달하도록 했습니다.

내 생각

1. visited 확인은 큐에 넣기 전에 하자.
2. 여러 조건을 탐색할때 가장 크게 이동하는 조건을 우선 탐색하자.