https://www.acmicpc.net/problem/1697
수빈이는 1초에 -1칸, 1칸, 현재의 위치의 두배 위치로 이동이 가능함
수빈이가 동생을 찾는데 걸리는 최소 시간은?
입력
첫 번째 줄 : n k
n : 수빈의 위치
k : 동생의 위치
출력
수빈이가 동생을 찾는 가장 빠른 시간
수빈이가 n에서 조건대로 이동하여 k로 갈 수 있는 최단 거리를 구하는 문제입니다.
문제에서 수빈이가 이동할 수 있는 경우는 [ 앞으로 한 칸, 뒤로 한 칸, 현재 위치 2배 ]로 총 3가지 입니다.
BFS는 알고리즘 특성 상 그래프에서 특정 위치에 가장 먼저 도착하는 시간을 알 수 있습니다.
따라서 현재 이동 가능한 모든 경우의 수를 Queue에 삽입하고 연산하는 과정을 k에 도달할 때까지 반복하면 됩니다.
https://angelplayer.tistory.com/404
from collections import deque
def bfs(n):
global k, ans
q = deque()
q.append(n)
dis[n] = 0
while q:
px = q.popleft()
nx = [px - 1, px + 1, px * 2]
for nxt in nx:
if nxt < 0 or nxt >= 100001:
continue
if dis[nxt] != -1:
continue
dis[nxt] = dis[px] + 1
q.append(nxt)
n, k = list(map(int, input().split()))
dis = [-1] * 100001
ans = 0
bfs(n)
print(dis[k])
~~
해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.
혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!
python source : https://github.com/ssh5212/conding-test-practice
java source : https://github.com/ssh5212/coding-test-java
[BOJ / 백준] 11899 괄호 끼워넣기 (S3^ / Stack) - Python (0) | 2024.07.05 |
---|---|
[BOJ / 백준] 1389 케빈 베이컨의 6단계 법칙 (S1 / BFS) - Python (1) | 2024.07.04 |
[BOJ / 백준] 2668 숫자고르기 (G5^ / DFS) - Python (0) | 2024.07.02 |
[BOJ / 백준] 16562 친구비 (G4 / DFS) - Python (0) | 2024.06.30 |
[Softeer/소프티어] 나무 섭지 (Lv3 / BFS) - Python (0) | 2024.06.29 |