- ๊ฐ์ ๊น์ด์ ํ์ ์๋ ๊ฒฝ์ฐ๋ ๋ฐฉ๋ฌธํ๋ ๊ณณ์ ํ ๋ฒ ๋ ์ฌ๋ฐฉ๋ฌธํ ์ ์๊ฒ ํด์ค๋ค.
- visit[x][1]์ ์ฌ๊ธฐ๊น์ง ์ค๋ ๊ฒฝ๋ก๊ฐ ๋ช ๊ฐ์ง์๋๋(๊ฒฝ์ฐ์ ์)๋ฅผ ๋ํ๋ด๋ฉฐ ์ต์ข ์ ์ผ๋ก ์ฌ๊ธฐ์ ๋ฐฉ๋ฌธํ๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ค ๋ํ ๊ฐ์ ๋ํ๋ด์ผ ํ๋ฏ๋ก(์ดํฉ) ์ถ๊ฐ์ ์ผ๋ก ๊ณ์ ๋ํด์ค์ผ ํ๋ค. ์ด ๋ถ๋ถ์ +1๋ก ์ค์ ํด์ ์ค๋ฅ ๋ฐ์
from collections import deque
def bfs():
q = deque([N])
visit[N] = [1, 1]
while q:
X = q.popleft()
if X == K:
return visit[X][0] -1, visit[X][1]
for x in (X - 1, X + 1, 2 * X):
if -1 < x < 100001:
# print(x, visit[:10])
if visit[x][0] == 0:
visit[x][0] = visit[X][0] + 1
visit[x][1] = visit[X][1]
q.append(x)
# ์ฌ๋ฐฉ๋ฌธ ๊ฐ๋ฅ: ๊ฐ์ ๊น์ด์ ํ์์ ๋ฐฉ๋ฌธํ์ ๊ฒฝ์ฐ! visit[X][0]์ ๊ฒฐ๊ตญ ๊น์ด๋ฅผ ๋ํ๋ด๊ธฐ ๋๋ฌธ
elif visit[x][0] == visit[X][0] + 1:
# ์ฌ๊ธฐ๊น์ง ์ค๊ธฐ ์ํด ๊ฑฐ์ณค๋ ๊ฒฝ๋ก๊ฐ visit[X][1]์ ์ ์ฅ๋์ด ์์ผ๋ฉฐ ์ด ๊ฐ๋ค์ ์ดํฉ์ visit[x][1]์ ์ ์ฅํด์ผ ํ๋ค. ์ถ๊ฐ์ ์ผ๋ก ๊ณ์ ๋ํด์ค์ผ ํจ
visit[x][1] += visit[X][1]
N, K = map(int, input().split())
visit = [[0, 0] for _ in range(100001)]
print('\n'.join(map(str, bfs())))
- N > K ์ธ ๊ฒฝ์ฐ๋ ๋ฌด์กฐ๊ฑด -1 ํ๋ ๋ฐฉ์ ๋ฐ์ ์๊ธฐ ๋๋ฌธ์ ๊ฒฝ๋ก๋ N - K, ๋ฐฉ์์ ํ๋๋ค. N == K ์ธ ๊ฒฝ์ฐ๋ ๋์ผํ๋ฏ๋ก ์์ธ์ฒ๋ฆฌ๋ก ๋นผ์ค๋ค
- ๊ฐ์ ๊น์ด์ ์์นํ ํ๊ฐ ํ ๋ฒ ๋๊ณ ๋๋ฉด ์๋์ผ๋ก ์ข ๋ฃ๋๊ณ ๊ทธ ํ์์ ์ป์ด๋ธ ๋ค์ ์์น์ ๊ฐ์ด ๋ค์ด์๋ ํ๋ก ๊ฐฑ์ ์์ผ์ค๋ค. ์ด ๊ฒฝ์ฐ ๊ฐ์ ๊น์ด์ ํ์์๋ ์ฌ๋ฐฉ๋ฌธ์ด ๊ฐ๋ฅํ๋๋ก ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ ํ๊ฐ ์ข ๋ฃ๋ ํ ์ผ๊ด์ ์ผ๋ก ์ฒ๋ฆฌํ๋ค. depth๋ ํ๊ฐ ํ ๋ฒ ๋ ๋๋ง๋ค 1์ฉ ์ถ๊ฐํ๋ค.
- ์ต์ข ์ ์ผ๋ก depth์ visit[K] ๊ฐ๋ง ์ถ๋ ฅํ๋ฉด ๋๋ค.
def bfs():
global depth
start = [N]
while 1:
for s in start:
visit[s] += 1
if visit[K] != 0:
break
depth += 1
q = []
for s in start:
if s - 1 > 0 and visit[s - 1] == 0:
q.append(s - 1)
if s + 1 < 100001 and visit[s + 1] == 0:
q.append(s + 1)
if s * 2 < 100001 and visit[s * 2] == 0:
q.append(s * 2)
start = q
N, K = map(int, input().split())
depth = 0
visit = [0] * 100001
if N >= K:
print(N - K)
print(1)
else:
bfs()
print(depth)
print(visit[K])
5 237
10
5
1 3
2
2
1 4
2
2
1 7
4
4
๊ฐ์ฅ ๋น ๋ฅธ ์๊ฐ๊ณผ ๊ฐ์ฅ ๋น ๋ฅธ ๋ฐฉ๋ฒ์ ๊ฐ์
๊ธฐ๋ณธ์ ์ผ๋ก ๋๋น ์ฐ์ ํ์์ ํ์์ ๋ฒ์๋ฅผ ํ ๋จ๊ณ์ฉ ๋ํ๊ฐ๋ฉด์ ํ์ํ๋ ๋ฐฉ์์ด๋ค. ์ฝ๋์์ผ๋ก๋ ํ์์ ์์๋ฅผ ํ๋์ฉ ๊บผ๋ด์ ์ฌ์ฉํ๋ ๋ฐฉ์์ฒ๋ผ ๋ณด์ด์ง๋ง ๊ธฐ์ค์ด ๋๋ ๋จ๊ณ(1์ด, ๋๋ ๊ฑฐ๋ฆฌ1)์ ๋ฐ๋ผ ํ๊ฐ ๋จ๊ณ๋ณ๋ก ๋๋ ์ ์๋ค.
๋ง์ฝ 1๋ถํฐ ํ์์ ์์ํ๋ค๋ฉด ์๊ฐ์ด ์ฆ๊ฐํจ์ ๋ฐ๋ผ ํ์ ๋ด๊ธฐ๊ฒ ๋๋ ์ซ์๋ ์๋์ ๊ฐ๋ค.
"""
1. ์ด์ ์ ํ์ ํ ๋ฒ์ด๋ผ๋ ๋ด๊ฒผ๋ ์ซ์๋ ์ ์ธ(๋ฐฉ๋ฌธ ์ฒ๋ฆฌ)
2. 0๋ณด๋ค ํฌ๊ณ 10๋ง๋ณด๋ค ์์ ์ซ์๋ง
"""
# 0์ด
queue = [1]
# 1์ด
queue = [2, 2]
# 2์ด
queue = [3, 4, 3, 4]
# 3์ด
queue = [6, 5, 8, 6, 5, 8]
๋ง์ฝ ์ฐพ์ผ๋ ค๋ K์ ๊ฐ์ด 8์ด๋ผ๋ฉด ๊ฐ ๋จ๊ณ๋ณ๋ก ํ๋ฅผ ํ์ํ๋ค๊ฐ 8์ด๋ ์ซ์๊ฐ ์ฒ์ ๋ฑ์ฅํ์ ๋, ๊ทธ๋์ ์ด(๊ฐ์ฅ ๋น ๋ฅธ ์๊ฐ
)์ ํ์ ๋ด๊ฒจ์๋ 8์ ๊ฐ์(๊ฐ์ฅ ๋น ๋ฅธ ๋ฐฉ๋ฒ์ ๊ฐ์
)๋ฅผ ๊ตฌํ๋ฉด ๋๋ค.
๋จ, ์ด๋ ์ด๋ฏธ ์ด์ ์ ํ ๋ฒ ํ์ ํ ๋ฒ์ด๋ผ๋ ์์๋ ๊ฐ์ ๋ค์ ํ์์ ์ค๋ณตํ์ํ๋ฉด ์๊ฐ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ฏ๋ก ๋ฐ๋ก ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ฅผ ํด์ค์ผ ํ๋ค. ์ฃผ์ํด์ผํ ์ ์ ํ๋ฅผ ํ์ํ๋ ๋์ค์ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ฅผ ํด์ฃผ๊ฒ ๋๋ฉด ๋ฐฉ๋ฒ์ ๊ฐ์๋ฅผ ๊ตฌํ ์ ์๋ค. ๋ฐฉ๋ฒ์ ๊ฐ์๋ ํ์ฌ ๋จ๊ณ์์ ์ค๋ณต๋๋ ์ซ์๋ฅผ ์ ๋ถ๋ค ๊ตฌํ ์ ์์ด์ผ ํ๋ค. ๊ทธ๋์ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ ๋จ๊ณ๋ณ ํ ํ์์ด ๋๋ ํ ๋ง์ง๋ง์ ํ๊บผ๋ฒ์ ์ฒ๋ฆฌํ๋ค.
1์ด๋ฅผ ๊ธฐ์ค ๋จ๊ณ๋ก ํ์ํ๊ธฐ ๋๋ฌธ์ ์๊ฐ์ ๋ํ ์ ๋ณด๋ ๋ฐ๋ก ํ์ ์ถ๊ฐํ ํ์ ์์ด ํ ํ์์ด ๋๋ ๋๋ง๋ค 1์ฉ ์ฆ๊ฐ์์ผ์ค๋ค.
# ์จ๋ฐ๊ผญ์ง 2
N, K = map(int, input().split())
def sol():
if N >= K:
return N-K, 1
queue = [N]
time = 0
visited = [0]*100001
visited[N] = 1
while queue:
new_q = []
for x in queue:
for y in (x-1, x+1, 2*x):
if y<0 or y>100000 or visited[y]:
continue
new_q.append(y)
time += 1
# K๋ฅผ ๋ฐ๊ฒฌํ๋ค๋ฉด ์ต๋จ ์๊ฐ๊ณผ ๋ฐฉ๋ฒ์ ๊ฐ์ ์ถ๋ ฅ
if K in new_q:
return time, new_q.count(K)
# ์ด์ ๋จ๊ณ์ ํ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ
for x in new_q:
visited[x] = 1
queue = new_q[:]
result = sol()
print('\n'.join(map(str, result)))