[DFS/BFS/완전탐색] 1697번 - 숨바꼭질(BFS)

[백준] 1697번 - 숨바꼭질

풀이 시간: 40분 이내

 

1) 문제 해결 아이디어

코드를 짜는데는 10분 정도 걸렸는데 오류를 고치는데 시간을 허비했다.

이 문제 같은 경우는 수빈이와 동생의 위치가 N, K로 주어졌을 때 수빈이가 동생을 찾을 수 있는

최소 시간을 구하는 문제로 BFS로 풀 수 있는 문제였다. 

 

이 문제에서는 N, K 값이 해당 범위 내에서 어떤 값이 들어올지 모르기 때문에

입력되는 N, K의 범위를 잘 확인한 후 리스트를 생성해야한다.

N, K가 각각 0 이상 100,000 이하로 범위가 주어졌기 때문에

크기가 100,001인 리스트(graph)를 생성했다. 평소에는 범위를 잘 확인하지 않아도 문제를 푸는데 지장이 없는 경우도 많았지만 이 문제의 경우는 주어진 범위를 보고 리스트 크기를 설정해야하기 때문에 범위 확인이 매우 중요한 부분이었다.  오늘의 교훈: 범위 확인을 잘하자!!!!!!!!!!!!!!!!!

 

첫번쨰 오류. 런타임 에러: IndexError

0 <= N, K < 100,000 으로 착각하여 graph 크기를 100,000으로 생성하고

그에 따라 bfs() 내 범위 검사에서 0 <= i < 100,000으로 설정하면서 오류가 발생했다.

 

Q. 최소 시간이 graph[k]가 아닌 (graph[k] - 1) 인 이유는?

실제로 걸리는 최소 시간은 그래프의 해당 위치에 있는 값에서 -1을 한 값을 출력해야 한다.

그 이유는 처음 시작하는 곳의 값이 1이기 때문이다.

 

2) 소스코드

from collections import deque
# 수빈, 동생 위치
n, k = map(int, input().split())
graph = [0] * (100001)

# BFS
def bfs(x):
  queue = deque()

  # 시작 지점 삽입, 방문 처리
  queue.append(x)
  graph[x] = 1

  while queue:
    x = queue.popleft()
    if(x == k):
      break
    # 이동 방식 3가지
    nx = [x - 1, x + 1, x * 2]
    
    for i in nx:
      if(0 <= i <= 100000):
        # 방문하지 않은 곳이면
        if(graph[i] == 0):
          # 삽입, 방문 처리
          queue.append(i)
          graph[i] = graph[x] + 1
        
bfs(n)
print(graph[k] - 1)