https://www.acmicpc.net/problem/1697
์๋น์ด๋ 1์ด์ X-1, X+1, 2*X๋ก ์ด๋ํ ์ ์๋ค. ๋์์ ์์น๋ก ์ด๋ํ๊ธฐ๊น์ง ๊ฑธ๋ฆฌ๋ ๊ฐ์ฅ ์์ ์๊ฐ์ ๊ตฌํ๋ผ
DFS ๋ฌธ์ ๋ก ํ๋ฅผ ์ฌ์ฉํ๋ค.
ํ์ฌ ์๋น์ด์ ์์น๋ฅผ ํ์ ๋ฃ๊ณ , ๊ทธ ์์น์์ X-1, X+1, 2*X๋ก ์ด๋์ํจ ํ visted[]์ 1์ ํ๋์ฉ ๋ํด ์ด๋์ ๊ฑธ๋ฆฐ ์๊ฐ์ ์ ์ฅํ๋ค.
๊ฐ ์ ์๋ ์์น๊ฐ 0<=x<=100000์ผ๋ก ํ๊ณ๊ฐ ์๊ธฐ ๋๋ฌธ์, visited[] ๋ฐฐ์ด๋ ๊ทธ ํฌ๊ธฐ๋งํผ ๋ฏธ๋ฆฌ ๋ง๋ค์๊ณ , ๋ฐฉ๋ฌธํ๋์ง ํ๋ณํ ๋๋ x๊ฐ ์ด ์์น๋ฅผ ๋ฒ์ด๋๋์ง ์ฒดํฌํด์คฌ๋ค.
from collections import deque
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
visited = [0]*(100001)
def bfs (node, visited, k):
queue = deque([node])
while queue:
x = queue.popleft()
if x==k:
print(visited[k])
return
for i in (x-1, x+1, x*2):
if 0<=i<=100000 and visited[i]==0:
queue.append(i)
visited[i] = visited[x]+1
bfs(N, visited, K)
while ์์ for๋ฌธ์ด ๋ค์ด๊ฐ์ n^2์ธ๊ฐ ํท๊ฐ๋ฆฌ๊ธด ํ์ง๋ง..
visitted[]๋ฅผ ์ด์ฉํด ํ๋ฒ ๋ฐฉ๋ฌธํ ๋ ธ๋๋ ๋ฐฉ๋ฌธํ์ง ์์ผ๋ฏ๋ก O(n)์ด ๊ฑธ๋ฆฐ๋ค๊ณ ์๊ฐํ๋ค.
deque๋ ์ฒ์ ์จ๋ณด๊ธฐ๋ ํ๊ณ , list๋ก๋ ๊ตฌํํ ์ ์์๊น? ์ถ์๋๋ฐ list์ pop(0)๋ ์๊ฐ๋ณต์ก๋๊ฐ O(n)์ด ๊ฑธ๋ฆฐ๋ค๊ณ ํ๋ค.
์ฒ์์๋ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๊ธฐ ์ํด dp๋ฅผ ์ด์ฉํ ๊น ์๊ฐํ์๋๋ฐ BFS๋ฅผ ๊ณต๋ถํด๋ณด๊ณ ์ถ์ด์ BFS๋ฅผ ํ์๋ค. ํจ์ฌ ์ฝ๋๊ฐ ๊ฐ๊ฒฐํด์ ์ข์ ๊ฒ ๊ฐ๋ค. dp๋ก๋ ์ถฉ๋ถํ ๊ตฌํํ ์ ์๋ ๋ฌธ์ ๊ฐ๋ค