[๋ฐฑ์ค-13549] ์จ๋ฐ๊ผญ์ง 3 / Python
๐ Problem Solving/Baekjoon
13549๋ฒ: ์จ๋ฐ๊ผญ์ง 3
์๋น์ด๋ ๋์๊ณผ ์จ๋ฐ๊ผญ์ง์ ํ๊ณ ์๋ค. ์๋น์ด๋ ํ์ฌ ์ N(0 ≤ N ≤ 100,000)์ ์๊ณ , ๋์์ ์ K(0 ≤ K ≤ 100,000)์ ์๋ค. ์๋น์ด๋ ๊ฑท๊ฑฐ๋ ์๊ฐ์ด๋์ ํ ์ ์๋ค. ๋ง์ฝ, ์๋น์ด์ ์์น๊ฐ X์ผ
www.acmicpc.net
from collections import deque
n, k = map(int, input().split())
graph = [0] * 100001
dx = [-1, 1, 2]
def bfs(start):
queue = deque()
queue.append(start)
while queue:
x = queue.popleft()
if x == k:
print(graph[x])
break
for i in range(3):
if i == 2:
nx = x * dx[i]
else:
nx = x + dx[i]
if 0 <= nx < 100001 and graph[nx] == 0:
if nx == x * 2 and x != 0:
graph[nx] = graph[x]
queue.appendleft(nx)
else:
graph[nx] = graph[x] + 1
queue.append(nx)
bfs(n)
ํด์ค
์ด์ ์ค๋ฒ์์ ํ์๋ ์จ๋ฐ๊ผญ์ง ๋ฌธ์ ์ ๋น์ทํ ๋ฌธ์ ๋ค. ๋ค๋ง 2*x๋งํผ ์ด๋ํ ๋ ์์๋๋ ์๊ฐ์ด 0์ด๋ผ๋ ๋ถ๋ถ์์ ๋ฌ๋๋ค. 2*x๋งํผ์ ์ด๋์ 0์ด๊ฐ ์์๋๋ฏ๋ก graph[x]์ ๊ฐ์ ๊ฐ์ผ๋ก ์ ์ฅํ๊ณ deque์๋ appendleft๋ก ์ฐ์ ์์๋ฅผ ๋์ฌ์ค์ ํ์๋ค.๐
'๐ Problem Solving > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-2468] ์์ ์์ญ / Python (0) | 2021.05.23 |
---|---|
[๋ฐฑ์ค-2583] ์์ญ ๊ตฌํ๊ธฐ / Python (0) | 2021.05.22 |
[๋ฐฑ์ค-1916] ์ต์๋น์ฉ ๊ตฌํ๊ธฐ / Python (0) | 2021.05.20 |
[๋ฐฑ์ค-1753] ์ต๋จ๊ฒฝ๋ก / Python (0) | 2021.05.20 |
[๋ฐฑ์ค-1912] ์ฐ์ํฉ / Python (0) | 2021.05.19 |