백준 1697번 숨바꼭질 문제 bfs 파이썬 풀이

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

 

백준 1697번 숨바꼭질

안녕하세요 코딩테스트 공부를 차갑게 하는 coldmans입니다.

 

오늘은 백준 1697번 숨바꼭질 문제를 풀어보겠습니다.

이 문제의 정답률은 25%로, 실버 1 난이도 문제 치고는 다소 낮은 편입니다.

왜 그런지 생각해보면, 이 문제를 다이내믹 프로그래밍(DP) 방식으로 접근하는 분들이 많기 때문입니다. DP 방식으로 테이블을 만들어 해결하려는 시도는 좋은 아이디어이지만, 이 문제에서는 적합하지 않습니다.

그 이유를 살펴보겠습니다:

 

다이내믹 프로그래밍 접근의 문제점

1. 상태 공간의 크기: 다이나믹 프로그래밍 접근법에서는 각 위치에서 최적의 해를 저장하고 갱신해야 합니다. 수빈이가 이동할 수 있는 모든 경우의 수를 고려하면 상태 공간의 크기가 매우 큽니다. 특히 2∗X로 이동하는 경우를 고려하면 상태 공간이 기하급수적으로 증가합니다.
2. 메모리 사용량: N과 K가 최대 100,000이기 때문에 모든 상태를 저장하려면 메모리 사용량이 매우 큽니다. 이는 현실적인 메모리 제한을 초과할 가능성이 높습니다.
3. 갱신 조건의 복잡성: 각 상태에서 이동할 수 있는 경우의 수가 세 가지 (X-1, X+1, 2*X)이기 때문에 모든 상태를 갱신하는 것이 복잡하고, 이를 최적화하기 어렵습니다.

따라서 다이나믹 프로그래밍으로 접근하기보다 너비 우선 탐색 즉 BFS를 사용하면 효율적으로 해결할 수 있습니다.

BFS는 모든 간선의 가중치가 동일할 때 최단 경로를 찾는 데 적합하죠?

이 문제에서는 이동하는데 걸리는 시간이 모두 1초로 동일하므로 각 위치마다 한 번씩만 방문하면서 초를 늘려가면 됩니다!, BFS가 적합하겠죠?

BFS에 대한 자세한 설명은 따로 포스팅하겠습니다.

 

from collections import deque

def find_min_time(n, k):
    if n >= k:
        return n - k

 

• 먼저 필요한 모듈 deque를 collections에서 가져옵니다. deque는 양쪽에서 빠른 시간 안에 삽입과 삭제를 지원하는 큐 자료구조입니다.
• find_min_time 함수는 출발위치 n와 도착위치 k를 인자로 받습니다.
• 출발위치가 도착 위치보다 크거나 같다면, 뒤로 걷기만 하면 되므로 걸리는 시간은 n - k 초가 됩니다. (만약 출발이 5이고 도착이 2라면 결국 곱하거나 더하는 건 의미 없고 빼기만 하면 되기 때문이죠)

    max_pos = 100000
    visited = [0] * (max_pos + 1)
    q = deque([(n, 0)])  # (현재 위치, 현재 시간)
    visited[n] = 1

 

 

 

• max_pos는 문제에서 주어진 위치의 최댓값인 100,000으로 설정합니다.
• visited 리스트는 각 위치를 방문했는지 여부를 체크합니다. 초기값은 모두 0으로 설정하고, 방문한 위치는 1로 표시합니다.
• 큐 q를 초기화합니다. 큐에는 현재 위치와 현재 시간을 튜플 (n, 0)의 형태로 저장합니다. 수빈이의 초기 위치 n과 초기 시간 0을 큐에 넣습니다.
• 수빈이의 초기 위치를 방문했으므로, visited[n]을 1로 설정합니다.

    while q:
        current_pos, current_time = q.popleft()
        
        # 다음 가능한 위치들
        next_positions = [current_pos - 1, current_pos + 1, current_pos * 2]

 

 

• 큐가 빌 때까지 반복문을 실행합니다.
• q.popleft()를 통해 큐의 왼쪽에서 현재 위치와 현재 시간을 가져옵니다.
• 다음으로 이동할 수 있는 위치들을 next_positions 리스트에 저장합니다. 이 위치들은 current_pos - 1, current_pos + 1, current_pos * 2입니다.

        for next_pos in next_positions:
            if 0 <= next_pos <= max_pos and visited[next_pos] == 0:
                if next_pos == k:
                    return current_time + 1
                q.append((next_pos, current_time + 1))
                visited[next_pos] = 1

 

 

• 다음 가능한 위치들을 하나씩 확인하면서 다음과 같은 조건을 검사합니다:
  • next_pos가 유효한 범위 내에 있어야 합니다 (0 ≤ next_pos ≤ 100,000).
  • next_pos를 이전에 방문한 적이 없어야 합니다 (visited[next_pos] == 0).
• 만약 next_pos가 동생의 위치 k와 같다면, 현재 시간에서 1초를 더해 반환합니다.
• 그렇지 않다면, next_pos와 다음 시간을 큐에 추가하고, next_pos를 방문한 것으로 표시합니다.

# 입력 받기
n, k = map(int, input().strip().split())
print(find_min_time(n, k))

 

 

• 입력을 받아 n과 k에 저장합니다.
• find_min_time 함수를 호출하고, 결과를 출력합니다.

 

아래는 전체 코드입니다.

from collections import deque

def find_min_time(n, k):
    if n >= k:
        return n - k
    
    max_pos = 100000
    visited = [0] * (max_pos + 1)
    q = deque([(n, 0)])  # (현재 위치, 현재 시간)
    visited[n] = 1
    
    while q:
        current_pos, current_time = q.popleft()
        
        # 다음 가능한 위치들
        next_positions = [current_pos - 1, current_pos + 1, current_pos * 2]
        
        for next_pos in next_positions:
            if 0 <= next_pos <= max_pos and visited[next_pos] == 0:
                if next_pos == k:
                    return current_time + 1
                q.append((next_pos, current_time + 1))
                visited[next_pos] = 1

# 입력 받기
n, k = map(int, input().strip().split())
print(find_min_time(n, k))

 

이번 포스팅에서는 백준 1697번 숨바꼭질 문제를 BFS 알고리즘을 활용하여 해결하는 방법을 설명했습니다. BFS를 통해 최단 경로를 찾는 방식이 이 문제에 적합한 이유와, 다이내믹 프로그래밍 방식이 왜 비효율적인지에 대해서도 알아보았습니다.

이 문제를 통해 BFS 알고리즘의 강력함과 효율성을 체감할 수 있었을 것입니다. BFS는 모든 경로가 동일한 가중치를 가질 때 최적의 해를 제공하며, 이를 통해 복잡한 문제도 효율적으로 해결할 수 있습니다. 다양한 문제에서 BFS를 활용해 보는 경험을 통해 알고리즘 실력을 더욱 향상할 수 있을 것입니다.