숨바꼭질 [백준 1697] - python

 

def BOJ1679():
  n, k = map(int, input().split())
  graph = [1e9] * 100001
  queue = []
  graph[n] = 0
  queue.append([n, 0])
  while queue:
    current_node, current_time = queue.pop(0)

    next_node = current_node - 1
    if 0 <= next_node <= 100000 and graph[next_node] > current_time + 1:
      graph[next_node] = min(graph[next_node], current_time + 1)
      queue.append([next_node, current_time + 1])

    next_node = current_node + 1
    if 0 <= next_node <= 100000 and graph[next_node] > current_time + 1:
      graph[next_node] = min(graph[next_node], current_time + 1)
      queue.append([next_node, current_time + 1])

    next_node = current_node * 2
    if 0 <= next_node <= 100000 and graph[next_node] > current_time + 1:
      graph[next_node] = min(graph[next_node], current_time + 1)
      queue.append([next_node, current_time + 1])

  print(graph[k])


BOJ1679()

비슷한 문제가 네이버 인턴 문제에도 나왔던걸로 기억한다. 그것보다 쉬운 버전이다.

 

 

접근방법 :

1. 모든 지점에 대한 순차적 탐색이 필요하다  => bfs

2. 초기값을 큰 수로 둔 배열을 선언후에 매번 해당 지점에 접근할때마다 값을 비교해서 갱신해 주었다

 

장애물 이었던 것 :

1. 시간에 대한 정보를 가지고 있는 쪽을 배열로 선언할지 dict로 선언할지 잘 파악해야 한다.
bfs를 사용할때 규칙적으로 값이 변하면 배열로, 불규칙적으로 변하면 dict로 선언하는 것이 신상에 좋다

 

 

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

1697번: 숨바꼭질