๐ญ ๋ฌธ์ ์ดํด
์๋น์ด๋ ๋์์ -1, +1, *2 ๋ผ๋ ์ธ ๊ฐ์ง์ ์ ํ์ง ์ค ํ๋๋ฅผ ๊ณจ๋ผ ์ด๋ํ๊ฒ ๋๋ค.
์ด๋ํ๋ ์ธ ๊ฐ์ง์ ์ ํ์ด ๋์์ 1์ด ์ฉ ์ฆ๊ฐํ๋ฏ๋ก ๋๋น ์ฐ์ ํ์์ ์ ํํ๋ค.
๊ฐ์ฅ ๋น ๋ฅธ ์๊ฐ์ ๊ตฌํ๊ณ ๊ฒฝ๋ก๋ฅผ ์ถ๋ ฅํด์ผํ๋ค.
ํ์ฌ ์์น ๋ฐ๋ก ์ง์ ๋ฒํธ๋ฅผ ๋ฐ๋ก ์ ์ฅํด๋๊ณ , ์ญ์ถ์ ํ๋ฉฐ ๋ฌธ์์ด๋ก ์ ์ฅํด ์ถ๋ ฅํ๋ค.
๊ตฌํ ์ธ์ด: Python
from collections import deque
def solve():
global n, k, sec, route
queue = deque()
# ์์์ ์ธํ
queue.append(n)
sec[n] = 0
route[n] = n
while queue:
now = queue.popleft()
for next in (now - 1, now + 1, now * 2):
if 0 <= next <= 100000:
if sec[next] == -1:
sec[next] = sec[now] + 1
queue.append(next)
# ๊ฒฝ๋ก ์ ์ฅ
route[next] = now
n, k = map(int, input().split())
sec = [-1] * 100001 # ์ด๋ ์๊ฐ ๊ธฐ๋ก
route = [0] * 100001 # ๊ฒฝ๋ก ๊ธฐ๋ก
answer = ''
solve()
print(sec[k])
while route[k] != k:
answer = str(k) + ' ' + answer
k = route[k]
answer = str(n) + ' ' + answer
print(answer[:-1])
'Problem_Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] ๋ฐฑ์ค 5014 ์คํํธ๋งํฌ / BFS (0) | 2021.01.13 |
---|---|
[BOJ] ๋ฐฑ์ค 13549 ์จ๋ฐ๊ผญ์ง 3 / BFS (0) | 2021.01.12 |
[BOJ] ๋ฐฑ์ค 12851 ์จ๋ฐ๊ผญ์ง 2 / BFS (0) | 2021.01.12 |
[BOJ] ๋ฐฑ์ค 1697 ์จ๋ฐ๊ผญ์ง / BFS (0) | 2021.01.07 |
[BOJ] ๋ฐฑ์ค 7569 ํ ๋งํ / BFS (0) | 2021.01.05 |