π λ¬Έμ μ΄ν΄
μλΉμ΄λ λμμ -1, +1, *2 λΌλ μΈ κ°μ§μ μ νμ§ μ€ νλλ₯Ό κ³¨λΌ μ΄λνκ² λλ€.
μ΄λνλ μΈ κ°μ§μ μ νμ΄ λμμ 1μ΄ μ© μ¦κ°νλ―λ‘ λλΉ μ°μ νμμ μ ννλ€.
μ£Όμν΄μΌν μ μ΄ μμλ€.
1. (νμ¬ μμΉ, κ±°κΈ°κΉμ§ κ±Έλ¦° μ΄) λ₯Ό ννλ‘ νμ μ μ₯ν΄μ μ¬μ©
κ° μ νμ§κ° μ΄λνλ λ°©λ²μ λ°λΌ μκ°μ΄ λ€λ₯΄λ―λ‘, μ΄λνλ κ²μ λ°λΌ κ±Έλ¦° μκ°μ κ°μ΄ 보κ΄νλ€.
2. λ°©λ¬Έ 체ν¬κ° νμμ΄λ€.
λ°©λ¬Ένλ μ§μ μ λ€μ λ°λ κ²μ μλ―Έμλ κ²μ΄λ€.
μ€μ»· μ΄λνλ€κ° λ€μ κ°μ μ§μ μ λ°λ κ²μ κ²°μ½ μ΅μ κ±°λ¦¬κ° λ μ μλ€. (+ μκ° μ΄κ³Ό 100%...)
ꡬν μΈμ΄: Python
from collections import deque
from sys import stdin
def solve():
global n, k, visited
queue = deque() # μμΉ, μκ°
queue.append((n, 0))
while queue:
loc, sec = queue.popleft()
if loc == k:
return sec
for move in (loc-1, loc+1, loc*2):
if 0 <= move <= 100000 and not visited[move]:
queue.append((move, sec+1))
visited[move] = True
return 0
n, k = map(int, stdin.readline().rstrip().split())
visited = [False] * (100000+1)
visited[n] = True # μμ μ§μ λ¨Όμ λ°©λ¬Έ μ²λ¦¬
print(solve())
μ.... μ΄κ±΄ μ’ λ°λ³΄κ°μ§λ§....
ν° μ°¨μ΄λ μμ§λ§ λ©λͺ¨λ¦¬λ₯Ό μκ»΄λ³΄κ² λ€κ³
방문체ν¬νλ visited 리μ€νΈμ ν¬κΈ°λ₯Ό μλΉμ΄/λμ μ€ λ λ€μͺ½μ μλ μ¬λμ κΈ°μ€μΌλ‘ κ·Έλ§νΌλ§ μ¬μ©νμλ€.
BFSλ λ§κ² ꡬννλλ° κ³μ ν리길λ,,
λ€λ₯Έ λΆλ€μ νμ΄λ₯Ό μ°Ύμ보λ 리μ€νΈμ ν¬κΈ°λ₯Ό λ¬Έμ μ μ΅λ λ²μμΈ 100000μΌλ‘ μ‘μλκ³ νμλ€.
λ¬Έμ μ μμ λ 5μμ 17λ‘ μ΄λν λ,
5-10-9-18-17 μ΄λ κ² λ€μͺ½μ κ°λ€κ° λμμ¨λ€....
5-4-8-16-17 λ κ°λ₯νμ§λ§ λ€μͺ½μ λ°λμ κ±°μΉλ μΌμ΄μ€κ° μλ보λ€...νΈνΈ...
λΉ λ₯΄κ² νΈλ κ²λ μ€μνμ§λ§, λΉ λ₯΄κ³ μ ννκ² λ¬Έμ λ₯Ό νμ νμ!! μ«!!!
'Problem_Solving' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BOJ] λ°±μ€ 13913 μ¨λ°κΌμ§ 4 / BFS (0) | 2021.01.12 |
---|---|
[BOJ] λ°±μ€ 12851 μ¨λ°κΌμ§ 2 / BFS (0) | 2021.01.12 |
[BOJ] λ°±μ€ 7569 ν λ§ν / BFS (0) | 2021.01.05 |
[BOJ] λ°±μ€ 2644 μ΄μκ³μ° / BFS, DFS (0) | 2021.01.05 |
[BOJ] λ°±μ€ 2667 λ¨μ§λ²νΈλΆμ΄κΈ° / BFS, DFS (0) | 2021.01.04 |