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번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
'알고리즘' 카테고리의 다른 글
| 최소 힙[백준 - 1927] - python (0) | 2022.01.07 |
|---|---|
| 숨바꼭질 4 (0) | 2022.01.06 |
| 케빈 베이컨의 6단계 법칙 (0) | 2022.01.04 |
| 가장 큰 증가 부분 수열[백준 11055] - python (0) | 2022.01.02 |
| LCS [백준 9251] - python (0) | 2022.01.01 |
