[백준] 13549번 숨바꼭질3

숨바꼭질 3

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	123485	32084	21324	24.042%

문제

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

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

입력

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

출력

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

예제 입력 1

5 17

예제 출력 1

2

힌트

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

내 코드

680ms 나온다.

from collections import deque

def bfs(start):
    MAX_LIMIT = 100001
    queue = deque([start])
    steps = [-1] * MAX_LIMIT
    ways = [0] * MAX_LIMIT
    steps[start] = 0
    ways[start] = 1

    while queue:
        x = queue.popleft()
        
        # 동생과 만났을 경우
        if x == K:
            break
            
        for xx in (2 * x, x - 1, x + 1):
            if 0 <= xx < MAX_LIMIT:
                # 처음 방문이면
                if steps[xx] == -1:
                    if xx == 2 * x:
                        steps[xx] = steps[x]
                    else:
                        steps[xx] = steps[x] + 1
                    ways[xx] = ways[x]
                    queue.append(xx)

                # 재 방문이면
                if steps[xx] > -1 and steps[xx] == steps[x] + 1:
                    ways[xx] += ways[x]

    return steps[K]

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

print(bfs(N))

내 코드 수정

ways를 빼니 88ms 정도 나온다.

from collections import deque

def bfs(start):
    MAX_LIMIT = 100001
    queue = deque([start])
    steps = [-1] * MAX_LIMIT
    steps[start] = 0

    while queue:
        x = queue.popleft()

        # 동생과 만났을 경우
        if x == K:
            return steps[K]
            
        for xx in (2 * x, x - 1, x + 1):
            if 0 <= xx < MAX_LIMIT:
                # 처음 방문이면
                if steps[xx] == -1:
                    if xx == 2 * x:
                        steps[xx] = steps[x]
                    else:
                        steps[xx] = steps[x] + 1
                    if xx == 2 * x:
                        queue.appendleft(xx)
                    else:
                        queue.append(xx)

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

print(bfs(N))

chatGPT

이 문제는 BFS(너비 우선 탐색)를 사용해 해결할 수 있습니다. 기존 숨바꼭질 문제와의 차이는 **순간이동(0초 소요)**의 도입입니다. 이로 인해 순간이동 경로를 우선적으로 탐색해야 하며, 가중치가 다른 경로를 처리하기 위해 다익스트라 알고리즘 또는 deque를 이용한 가중치 처리를 사용해야 합니다.

---

해결 방법

1. 가중치에 따른 BFS 구현:
   • 순간이동(2*X)은 0초 소요되므로 우선 탐색해야 합니다.
   • X+1, X-1은 1초가 소요됩니다.
   • deque를 이용해 0초 이동은 앞쪽에, 1초 이동은 뒤쪽에 추가하는 방식으로 처리합니다.
2. 방문 처리:
   • 이미 방문한 위치를 다시 방문할 필요가 없으므로 visited 배열로 관리합니다.
3. 종료 조건:
   • BFS를 진행하며 동생의 위치 K에 도달하면 즉시 탐색을 종료하고 최소 시간을 출력합니다.

---

코드 구현

from collections import deque

def find_minimum_time(N, K):
    MAX = 100001  # 최대 범위(아래와 시간 차이 별로 안남)
    # MAX = min(max(N, K) * 2, 100001)  # 최대 범위
    visited = [-1] * MAX  # 방문 여부 및 시간 기록
    queue = deque([N])  # 시작 위치
    visited[N] = 0  # 시작 위치 시간 0

    while queue:
        current = queue.popleft()

        # 동생의 위치에 도달한 경우
        if current == K:
            return visited[current]

        # 3가지 이동
        for next_pos, time_cost in [(current * 2, 0), (current - 1, 1), (current + 1, 1)]:
            if 0 <= next_pos < MAX and visited[next_pos] == -1:
                visited[next_pos] = visited[current] + time_cost
                if time_cost == 0:  # 0초 소요 이동은 deque의 앞에 추가
                    queue.appendleft(next_pos)
                else:  # 1초 소요 이동은 deque의 뒤에 추가
                    queue.append(next_pos)

# 입력
N, K = map(int, input().split())
# 출력
print(find_minimum_time(N, K))

---

코드 설명

1. 초기 설정:
   • MAX = 100001로 방문 가능한 최대 범위를 설정합니다.
   • visited 배열은 방문 여부와 시간을 기록합니다. 초기값은 -1로 설정합니다.
2. BFS 탐색:
   • deque를 사용해 가중치에 따라 0초 이동을 우선적으로 처리합니다.
   • current * 2는 순간이동으로 시간 소요가 없으므로 appendleft로 추가합니다.
   • current - 1과 current + 1은 1초 소요되므로 append로 추가합니다.
3. 종료 조건:
   • 현재 위치가 동생의 위치와 같아지면 최소 시간을 반환합니다.

부가 질문

내 생각

1. 경로 수를 구하는게 없으므로 ways는 빼도 된다.
   1. 내 코드가 680ms, GPT 코드가 88ms 로 나왔으나, ways 를 빼니 내 코드도 88ms 정도로 나온다.
2. GPT 코드 MAX = 100001 과 MAX = min(max(N, K) * 2, 100001) 가 시간차이 얼마 안난다.
3. GPT 코드 queue.appendleft(next_pos) 해도 시간차이 얼마 안난다.