๐ก ๋ฌธ์
๐ก ํ์ด
์ฒ์์๋ ๋จ์ํ ๊ฐ๋จํ BFS ๋ฌธ์ ๋ผ๊ณ ์๊ฐํ์ฌ ์๋์ ๊ฐ์ด ์ฝ๋๋ฅผ ์์ฑํ๋๋ ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๊ฐ ๋ฌ์ต๋๋ค. ๊ทธ ์ด์ ๋ n๊ณผ k๊ฐ 100,000๊น์ง ๋ ์ ์๋๋ฐ, while๋ฌธ์ ๋๋ฉด์ queue
๊ฐ ๊ณ์ 3๋ฐฐ๊ฐ ๋๊ธฐ ๋๋ฌธ์
๋๋ค.
# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 1697 ์จ๋ฐ๊ผญ์ง
import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int, input().split())
answer = 0
queue = deque([])
queue.append([n, 0])
while queue:
i, cnt = queue.popleft()
if i == k:
answer = cnt
break
queue.append([i - 1, cnt + 1])
queue.append([i + 1, cnt + 1])
queue.append([i * 2, cnt + 1])
print(answer)
์ด๋ ๊ฒ ๋จ์ํ ํ์ -1ํ ๊ฐ, +1ํ ๊ฐ, x2ํ ๊ฐ์ ๋ฌด์กฐ๊ฑด ๋ฃ์ด์ฃผ๊ฒ ๋๋ฉด, ์ค๋ณตํด์ queue
์ ๋ฃ์ด์ง๊ฒ ๋๋ ๊ฐ์ด ๋งค์ฐ ๋ง์ต๋๋ค. ์ฆ, ํ๋ฒ ๊ฒ์ฌํ๋ ๊ฒ๋ค์ ๊ณ์ ๊ฒ์ฌํ๊ฒ ๋ฉ๋๋ค. ๋ฐ๋ผ์ queue
์ ๋ฃ๊ธฐ ์ ์ ์กฐ๊ฑด๋ฌธ์ ํตํด ๋ฐฉ๋ฌธํ์๋์ง ๊ฒ์ฌํ๋ ๊ฒ์ด ํ์ํฉ๋๋ค.
์ฒ์์ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ๊ฒ์ฌํ๋ ๋ฆฌ์คํธ๋ฅผ ๋ง๋๋ ๊ฒ์ ์๊ฐํ์๋๋ฐ, n
๊ณผ k
์ ๋ฒ์๊ฐ 10๋ง๊น์ง์ฌ์ ๋๋ฌด ํฌ๋ค๊ณ ์๊ฐํด์ ๋ฆฌ์คํธ๋ฅผ ๋ฐ๋ก ๋ง๋ค์ง ์์์ต๋๋ค. ๊ทธ๋ฌ๋ 1byte์ง๋ฆฌ boolean ๋ณ์๊ฐ 100,000๊ฐ์ด๋ฉด 100,000 byte = 100 KB ์ ๋๋ฐ์ ๋์ง ์์ผ๋ฏ๋ก ๋ฌธ์ ์์ ์ค 124MB ๋ฉ๋ชจ๋ฆฌ์์๋ ์ถฉ๋ถํ ์ฌ์ฉ ๊ฐ๋ฅํฉ๋๋ค.
๋ฐ์ฌ๋ฌ queue
์ ๋ฃ์ผ๋ ค๋ ๊ฐ์ด 0๊ณผ 100,000 ์ฌ์ด์ ๊ฐ์ธ์ง ํ์ธํ๊ณ , ํด๋น ๊ฐ์ ๋ฐฉ๋ฌธํ ์ ์ด ์๋ค๋ฉด queue
์ ๋ฃ์ด์ฃผ๋๋ก ์กฐ๊ฑด๋ฌธ์ ์ถ๊ฐํ์์ต๋๋ค.
๐ก ์ ๋ต ์ฝ๋
# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 1697 ์จ๋ฐ๊ผญ์ง
import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int, input().split())
answer = 0
visited = [False] * 1000001
queue = deque([])
queue.append([n, 0])
while queue:
i, cnt = queue.popleft()
if i == k:
answer = cnt
break
if 0 <= i - 1 <= 1000000 and not visited[i - 1]:
visited[i - 1] = True
queue.append([i - 1, cnt + 1])
if 0 <= i + 1 <= 1000000 and not visited[i + 1]:
visited[i + 1] = True
queue.append([i + 1, cnt + 1])
if 0 <= i * 2 <= 100000 and not visited[i * 2]:
visited[i * 2] = True
queue.append([i * 2, cnt + 1])
print(answer)
๋๊ธ