[BOJ] 백준 1697 숨바꼭질 / BFS

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

수빈이는 동시에 -1, +1, *2 라는 세 가지의 선택지 중 하나를 골라 이동하게 된다.

이동하는 세 가지의 선택이 동시에 1초 씩 증가하므로 너비 우선 탐색을 선택했다.

 

주의해야할 점이 있었다.

 

1. (현재 위치, 거기까지 걸린 초) 를 튜플로 큐에 저장해서 사용

각 선택지가 이동하는 방법에 따라 시간이 다르므로, 이동하는 것에 따라 걸린 시간을 같이 보관했다.

 

2. 방문 체크가 필수이다.

방문했던 지점을 다시 밟는 것은 의미없는 것이다.

실컷 이동하다가 다시 같은 지점을 밟는 것은 결코 최소 거리가 될 수 없다. (+ 시간 초과 100%...)

 

 

 

구현 언어: Python

 

 

from collections import deque
from sys import stdin


def solve():
    global n, k, visited
    queue = deque()  # 위치, 시간
    queue.append((n, 0))
    
    while queue:
        loc, sec = queue.popleft()
        if loc == k:
            return sec
        for move in (loc-1, loc+1, loc*2):
            if 0 <= move <= 100000 and not visited[move]:
                queue.append((move, sec+1))
                visited[move] = True
    return 0


n, k = map(int, stdin.readline().rstrip().split())
visited = [False] * (100000+1)
visited[n] = True  # 시작 지점 먼저 방문 처리

print(solve())

 

 

 

음.... 이건 좀 바보같지만....

 

큰 차이는 없지만 메모리를 아껴보겠다고

방문체크하는 visited 리스트의 크기를 수빈이/동생 중 더 뒤쪽에 있는 사람을 기준으로 그만큼만 사용했었다.

BFS는 맞게 구현했는데 계속 틀리길래,,

다른 분들의 풀이를 찾아보니 리스트의 크기를 문제상 최대 범위인 100000으로 잡아두고 풀었다.

 

 

문제의 예제도 5에서 17로 이동할 때,

5-10-9-18-17 이렇게 뒤쪽을 갔다가 돌아온다....

5-4-8-16-17 도 가능하지만 뒤쪽을 반드시 거치는 케이스가 있나보다...호호...

 

빠르게 푸는 것도 중요하지만, 빠르고 정확하게 문제를 파악하자!! 쫌!!!