https://www.acmicpc.net/problem/13913
์จ๋ฐ๊ผญ์ง ์๋ฆฌ์ฆ ๋ง์ง๋ง ์จ๋ฐ๊ผญ์ง 1 ๋จผ์ ํ์ด๋ณด๋ ๊ฒ ์ข๋ค.
์์ด๋์ด
1. bfs
- ํ์ x +1, x - 1, x * 2๋ฅผ ์กฐ๊ฑด์ ๋ง์ผ๋ฉด ์ถ๊ฐํด์ค๋ค.
- ํ์ ์์น์ ์๊ฐ ๊ทธ๋ฆฌ๊ณ ์ง๋์จ ๊ธธ๋ ๊ฐ์ด ๋ฃ์ด์ค๋ค.
- ๋์ฐฉํ๋ฉด ๋์ฐฉ ์๊ฐ๊ณผ ๊ฒฝ๋ก๋ฅผ ๋ฆฌํด ํ ์ถ๋ ฅ.
์ ์ฒด ์ฝ๋
from collections import deque
N, K = map(int,input().split())
visited = [False] * (200001)
def bfs(n):
deq = deque()
deq.append([n, 0,[n]])
visited[n] = True
if n > K:
return n - K, [int(x) for x in range(n,K - 1,-1)]
while deq:
x, count, road = deq.popleft()
if x == K:
return count, road
arr = [x - 1, x + 1, x * 2]
for a in arr:
if 0 <= a <= 100000 and visited[a] == False:
visited[a] = True
r = road + [a]
deq.append([a, count + 1, r])
ans_count, ans_road = bfs(N)
print(ans_count)
for path in ans_road:
print(path,end=' ')
์ฝ๋ ์ค๋ช
def bfs(n):
deq = deque()
deq.append([n, 0,[n]])
visited[n] = True
if n > K:
return n - K, [int(x) for x in range(n,K - 1,-1)]
while deq:
x, count, road = deq.popleft()
if x == K:
return count, road
arr = [x - 1, x + 1, x * 2]
for a in arr:
if 0 <= a <= 100000 and visited[a] == False:
visited[a] = True
r = road + [a]
deq.append([a, count + 1, r])
๊ธฐ์กด ์จ๋ฐ๊ผญ์ง ๋ฌธ์ ์ ๋งค์ฐ ์ ์ฌํ๋ค. ์ฐ๋ฆฌ๊ฐ ํ ๊ฑด ๊ฒฝ๋ก๋ง ๊ฐ์ด ์ ์ฅํด์ฃผ๋ฉด ๋๋ค.
๊ทผ๋ฐ ๊ทธ๋ฅ ์ด๋ ๊ฒ ํ๋ฉด 100000 0 ๊ฐ์ ์ ๋ ฅ์ด ๋ค์ด์ค๋ฉด ์๊ฐ ์ด๊ณผ๊ฐ ๋ฌ๋ค.
์ด๋ด ๋๋ ์ด๋ฏธ N๋ณด๋ค K๊ฐ ํฐ ๊ฒฝ์ฐ ๋ฐ๋ก ์๊ฐํด์ค๋ค.
๋์ฐฉํ๋ ค๋ฉด ๋ค๋ก ๊ฐ๋ ๋ฐฉ๋ฒ(x - 1)๋ฟ์ด๋ฏ๋ก ์๊ฐ์ N - K
๊ฒฝ๋ก๋ N๋ถํฐ K๊น์ง 1์ฉ ๊ฐ์ํ๋ฉด ๋๋ค.
'๐งฉ Problem Solving > [๋ฐฑ์ค]' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 15654 N๊ณผ M(5) (python ํ์ด์ฌ) (0) | 2022.07.13 |
---|---|
[๋ฐฑ์ค] 1202 ๋ณด์ ๋๋ (python ํ์ด์ฌ) (0) | 2022.07.11 |
[๋ฐฑ์ค] 12851 ์จ๋ฐ๊ผญ์ง 2 (python ํ์ด์ฌ) (0) | 2022.07.10 |
[๋ฐฑ์ค] 1043 ๊ฑฐ์ง๋ง (python ํ์ด์ฌ) (0) | 2022.07.09 |
[๋ฐฑ์ค] 2467 ์ฉ์ก (python ํ์ด์ฌ) (0) | 2022.07.09 |