[BFS] 백준 1697 숨바꼭질

1697번: 숨바꼭질

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

1697번: 숨바꼭질

 

#1 문제 이해

• 수빈이의 위치 N (0<=N<=100,000) 과 동생의 위치 K ( 0<=K<=100,000) 가 주어졌을 때 수빈이가 현재 위치 X에서 X-1, X+1, 2*X 의 위치로 이동하며 동생을 찾는 최단시간을 구하는 문제이다.
• 예를 들어 수빈이의 위치가 5이고, 동생의 위치가 17이라면 수빈이는 5-10-9-18-17 순서로 이동하여 4초만에 동생을 찾을 수 있다.
• 너비 우선 탐색, 즉 BFS를 이용하면 쉽게 풀 수 있는 문제였다.

 

#2 어려웠던 부분

BFS에 대한 이해가 부족해 큐를 사용하지 않고 문제를 풀어내고 싶었다.

재귀함수를 이용해 풀어보려 했으나 X-1, X+1, 2*X 세 가지 경우에 대해 계속해서 재귀를 거는 경우 어느 한 쪽에서 X==K 가 되어 return으로 빠져나가더라도 나머지 경우들은 계속해서 재귀에 재귀가 중첩되어 함수 호출이 종료되지 않는 문제가 있었다.

파이썬의 경우 재귀 깊이 제한이 있기 때문에 재귀 함수가 어느정도 호출되면 다음과 같은 RecursionError를 띄운다.

• RecursionError: maximum recursion depth exceeded in comparison

재귀함수만을 이용해 문제를 풀 수 없다는 것을 깨닫고 나의 문제풀이는 쓰레기통으로 들어가게 되었다.

 

아래는 최종 코드를 작성할 때  참고한 블로그이다.

https://letalearns.tistory.com/34

[Python] 백준 1697번 - 숨바꼭질

 

아직 파이썬으로 큐를 사용하는 것이 익숙치 않아 더 어려웠던 것 같다.

이게 된다고??? 싶은 문법이 참 많기 때문이다........

문제를 더더 많이 풀고 손과 눈에 익혀야 겠다는 생각이 들었다.

• BFS 개념 및 deque 사용법

 

#3 최종 코드

from collections import deque

# 움직일 수 있는 최대 좌표는 100,000
MAX_NUM = 100000

def bfs(x):
    q = deque([x]) # 큐 구현을 위해 deque 사용
    while q:
        x = q.popleft() # 큐의 맨 앞에서 노드 추출
        if x == k: # 동생의 위치에 도달했을 때
            return visited[x] # 수빈이가 동생을 찾는데 걸린 시간 반환
        for i in (x-1, x+1, 2*x): # 수빈이의 다음 위치 후보들에 대해
            if 0 <= i <= MAX_NUM and not visited[i]: # 이동 가능한 범위 내에서
                visited[i] = visited[x] + 1 # 방문 표시 및 걸린 시간 기록
                q.append(i) # 다음 위치 후보를 큐에 추가

# 공백을 기준으로 N, K 입력값 받기
n, k = map(int, input().split())

visited = [0 for i in range(MAX_NUM + 1)] # 좌표마다 방문 여부 및 걸린 시간 기록

print(bfs(n)) # bfs 함수 호출하여 결과 출력

 

+

처음 참고했던 코드가 오답처리되어 새로 참고한 코드이다 :D