๐ญ ๋ฌธ์ ์ดํด
์๋น์ด๋ ๋์์ -1, +1, *2 ๋ผ๋ ์ธ ๊ฐ์ง์ ์ ํ์ง ์ค ํ๋๋ฅผ ๊ณจ๋ผ ์ด๋ํ๊ฒ ๋๋ค.
์ด๋ํ๋ ์ธ ๊ฐ์ง์ ์ ํ์ด ๋์์ 1์ด ์ฉ ์ฆ๊ฐํ๋ฏ๋ก ๋๋น ์ฐ์ ํ์์ ์ ํํ๋ค.
๊ฐ์ฅ ๋น ๋ฅธ ์๊ฐ์ผ๋ก ์ฐพ์๊ฐ๋ ๋ฐฉ๋ฒ์ด ์ด ๋ช ๊ฐ์ง์ธ์ง๋ ๊ตฌํด์ผ ํ๋ ๊ฒ์ด ํฌ์ธํธ์ด๋ค.
ํ์ฌ ๊ฒฝ๋ก๊น์ง์ cnt๊ฐ ๋ค์ ๊ฒฝ๋ก์๋ ํฉ์ฐ์ด ๋๋ฏ๋ก ๋ง์น ๋ถ๋ถ์ ์ผ๋ก dp ๋ฌธ์ ์ ๊ฐ์ ๋๋์ด ๋ค์๋ค.
๊ตฌํ ์ธ์ด: Python
from collections import deque
def solve():
global n, k, sec, cnt
queue = deque()
queue.append(n) # ์์์ ์ ๋จผ์ ๋ด๋๋ค.
sec[n] = 0
cnt[n] = 1
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
cnt[next] = cnt[now]
queue.append(next)
# ๋ฐฉ๋ฌธํ๋ ๊ณณ์ผ ๋,
# ์ด์ ์ ๊ธฐ๋ก๋ ์ต์ ์๊ฐ๊ณผ ๋์ผํ ์๊ฐ์ผ๋ก ๋์ฐฉํ ์ ์๋ ๊ฒฝ๋ก ์ถ๊ฐ
elif sec[next] == sec[now] + 1:
cnt[next] += cnt[now]
n, k = map(int, input().split())
sec = [-1] * 100001
cnt = [0] * 100001
solve()
print(sec[k])
print(cnt[k])
'Problem_Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] ๋ฐฑ์ค 13549 ์จ๋ฐ๊ผญ์ง 3 / BFS (0) | 2021.01.12 |
---|---|
[BOJ] ๋ฐฑ์ค 13913 ์จ๋ฐ๊ผญ์ง 4 / BFS (0) | 2021.01.12 |
[BOJ] ๋ฐฑ์ค 1697 ์จ๋ฐ๊ผญ์ง / BFS (0) | 2021.01.07 |
[BOJ] ๋ฐฑ์ค 7569 ํ ๋งํ / BFS (0) | 2021.01.05 |
[BOJ] ๋ฐฑ์ค 2644 ์ด์๊ณ์ฐ / BFS, DFS (0) | 2021.01.05 |