Yunsu's Log

BOJ 1697: 숨바꼭질

7 min read

Note

1D 그래프에서 BFS를 활용하여 수빈이가 동생을 찾는 최단 시간을 구하는 문제입니다.

문제 링크

문제 요약

수빈이는 현재 점 N에 있고, 동생은 점 K에 있습니다. 수빈이는 다음과 같이 이동할 수 있습니다:

  • 1초 후에 X-1 또는 X+1로 이동
  • 1초 후에 2*X의 위치로 순간이동

수빈이가 동생을 찾는 가장 빠른 시간을 구하세요.

  • 입력: 수빈이의 위치 N, 동생의 위치 K (0 ≤ N, K ≤ 100,000)
  • 출력: 수빈이가 동생을 찾는 가장 빠른 시간 (초)

핵심 아이디어

1D 그래프에서의 BFS

이 문제는 0부터 100,000까지의 정수들을 정점으로 하는 그래프에서 BFS를 수행하는 문제입니다.

각 정점 X에서 다음 정점으로 이동할 수 있는 방법:

  1. X-1: 왼쪽으로 1칸 이동 (1초)
  2. X+1: 오른쪽으로 1칸 이동 (1초)
  3. 2*X: 순간이동 (1초)

레벨별 탐색

BFS의 특성상 같은 거리(시간)의 위치들을 먼저 탐색하므로, 목표 지점에 도달하는 순간이 최단 시간입니다.

알고리즘 설계

1. 초기화

visited = [False for _ in range(100001)]
visited[n] = True
 
steps = deque([n])
next_steps = deque([])
s_count = 0
  • visited: 방문 여부를 저장하는 배열 (0~100,000)
  • steps: 현재 레벨의 위치들
  • next_steps: 다음 레벨의 위치들
  • s_count: 경과 시간 (초)

2. 레벨별 BFS

while steps:
    v = steps.popleft()
    
    if v == k:  # 목표 지점 도달
        break
    
    # 왼쪽으로 이동
    if v > 0 and visited[v - 1] == False:
        next_steps.append(v - 1)
        visited[v - 1] = True
    
    # 오른쪽으로 이동
    if v < 100000 and visited[v + 1] == False:
        next_steps.append(v + 1)
        visited[v + 1] = True
    
    # 순간이동
    if v * 2 <= 100000 and visited[v * 2] == False:
        next_steps.append(v * 2)
        visited[v * 2] = True
    
    # 현재 레벨이 끝나면 다음 레벨로
    if len(steps) == 0 and len(next_steps) > 0:
        steps = next_steps
        next_steps = deque([])
        s_count += 1

3. 결과 출력

print(s_count)

전체 코드

from collections import deque
 
n, k = map(int, input().split())
 
def solve():
    visited = [False for _ in range(100001)]
    visited[n] = True
 
    steps = deque([n])
    next_steps = deque([])
    s_count = 0
    
    while steps:
        # print('steps:', steps)
        v = steps.popleft()
        # print('v:', v)
        if v == k:
            break
 
        # left
        if v > 0 and visited[v - 1] == False:
            next_steps.append(v - 1)
            visited[v - 1] = True
        # right
        if v < 100000 and visited[v + 1] == False:
            next_steps.append(v + 1)
            visited[v + 1] = True
        # multi    
        if v * 2 <= 100000 and visited[v * 2] == False:
            next_steps.append(v * 2)
            visited[v * 2] = True
 
        if len(steps) == 0 and len(next_steps) > 0:
            steps = next_steps
            next_steps = deque([])
            s_count += 1
 
    print(s_count)
 
solve()

코드 설명

1. 초기화

visited = [False for _ in range(100001)]
visited[n] = True
 
steps = deque([n])
next_steps = deque([])
s_count = 0
  • visited: 0부터 100,000까지의 위치 방문 여부
  • 시작 위치 n을 방문 표시하고 큐에 추가
  • s_count: 경과 시간 (초)

2. 레벨별 BFS

while steps:
    v = steps.popleft()
    
    if v == k:  # 목표 지점 도달
        break
    
    # 왼쪽으로 이동
    if v > 0 and visited[v - 1] == False:
        next_steps.append(v - 1)
        visited[v - 1] = True
    
    # 오른쪽으로 이동
    if v < 100000 and visited[v + 1] == False:
        next_steps.append(v + 1)
        visited[v + 1] = True
    
    # 순간이동
    if v * 2 <= 100000 and visited[v * 2] == False:
        next_steps.append(v * 2)
        visited[v * 2] = True
    
    # 현재 레벨이 끝나면 다음 레벨로
    if len(steps) == 0 and len(next_steps) > 0:
        steps = next_steps
        next_steps = deque([])
        s_count += 1
  • 현재 레벨(steps)의 모든 위치를 처리
  • 각 위치에서 세 가지 이동 방법을 시도
  • 범위 체크: 0 <= 위치 <= 100000
  • 방문하지 않은 위치만 next_steps에 추가
  • 현재 레벨이 끝나면 다음 레벨로 이동하고 시간 증가

3. 결과 출력

print(s_count)
  • 목표 지점에 도달한 시간 출력

시간 복잡도

  • 시간 복잡도: O(K)

    • 최악의 경우 0부터 K까지 모든 위치를 방문
    • 각 위치에서 세 가지 이동 방법 확인은 상수 시간

  • 공간 복잡도: O(100,000) = O(1)

    • 방문 배열: O(100,001)
    • 큐: 최악의 경우 O(100,000)

풀이 포인트

1. 레벨별 탐색

이 코드는 레벨별로 탐색하는 방식을 사용합니다:

  • steps: 현재 시간(레벨)의 위치들
  • next_steps: 다음 시간(레벨)의 위치들
  • 현재 레벨이 끝나면 다음 레벨로 이동하고 시간 증가

2. 범위 체크

  • 왼쪽 이동: v > 0 (0보다 작아질 수 없음)
  • 오른쪽 이동: v < 100000 (100,000을 넘을 수 없음)
  • 순간이동: v * 2 <= 100000 (100,000을 넘을 수 없음)

3. 방문 표시 시점

큐에 넣을 때 방문 표시를 해야 같은 위치가 여러 번 큐에 들어가는 것을 방지할 수 있습니다.

다른 구현 방법

거리 정보를 함께 저장하는 방법도 있습니다:

from collections import deque
 
n, k = map(int, input().split())
 
def solve():
    visited = [False] * 100001
    queue = deque([(n, 0)])  # (위치, 시간)
    visited[n] = True
    
    while queue:
        v, time = queue.popleft()
        
        if v == k:
            return time
        
        for next_pos in [v - 1, v + 1, v * 2]:
            if 0 <= next_pos <= 100000 and not visited[next_pos]:
                visited[next_pos] = True
                queue.append((next_pos, time + 1))
    
    return -1
 
print(solve())

이 방법이 더 간단하고 직관적입니다.

관련 문제

그래프 뷰

백링크