[python] 백준 - 1697. 숨바꼭질

문제 해결

1. BFS 기본 문제. S1

2. 주어진 범위 100,000까지의 배열을 만든다.

3. BFS를 활용해 현재위치와 다음위치를 배열에 넣고 while문을 돌린다 

 (1) 각 지점에 도달하기 까지의 최소 시간으로 업데이트 해준다.

 (2) 이렇게 코드를 짜는 경우 시간초과가 생길 수 있으므로 deque()를 사용하고

 (3) 한번도 방문한 적이 없거나, 최소시간으로 방문할 때만 다음 지점으로 나아갈 수 있게 한다.

4. 현재 위치가 목표 지점에 도달하면 break로 while문을 빠져나와 답을 출력한다.

 

🌞 처음에 범위를 100001까지 잡았더니 인덱스가 마지막이 될 경우에 런타임에러가 발생한다.

그래서 100002로 바꿔줬더니 해결했다.

재귀로 풀어 봤지만 maximum recursion depth exceeded 에러가 발생해서 BFS를 활용해 문제를 해결했다.

 

소스 코드

from _collections import deque


def bfs(c, n):
    # n 이 범위내에 존재하며
    # 한번도 방문한 적이 없거나, 방문한 적이 있다면 최소 시간으로 방문했을 때 탐색을 시작
    if 0 <= n < 100002 and (visit[n] == 0 or visit[n] > visit[c] + 1):
        visit[n] = visit[c] + 1
        q.append(n)


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

visit = [0]*100002
result = 0
q = deque()
q.append(N)

# while 문을 돌며 계속 탐색
while q:
    # 현재위치를 꺼내고
    current = q.popleft()

    # 정지 조건: 목표 지점에 도달하면 break로 while문을 빠져나온다. | visit[c]에는 도달 시간이 저장되어있다.
    if current == K:
        result = visit[current]
        break

    # 가능한 경우의수 3가지를 탐색한다.
    bfs(current, current-1)
    bfs(current, current+1)
    bfs(current, current*2)

print(result)

 

 

출처: BACKJOON ONLINE JUDGE

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

1697번: 숨바꼭질

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.