๐ฅ Silver1
https://www.acmicpc.net/problem/1697
๋ฉ๋ชจ๋ฆฌ | ์คํ์๊ฐ |
40316KB | 252ms |
โ ์ ๋ตํ์ด
import sys
from collections import deque
input = sys.stdin.readline
# ์ต๋จ๊ฒฝ๋ก ์ฐพ๊ธฐ=์ต๋จ์๊ฐ ์ฐพ๊ธฐ (bfs)
def bfs(start,target):
global cur
queue=deque([start])
visited[start]=0 #์์์ ์ ์ด๋๊ฑฐ๋ฆฌ=0
while queue:
cur=queue.popleft()
if cur==target:
return visited[cur]
for i in range(3):
if i<2:
nx=cur+dx[i]
else:
nx=cur*dx[i]
if 0 <= nx <= max(n, m) * 2 and visited[nx] == -1:
visited[nx]=visited[cur]+1
queue.append(nx)
n, m = map(int, input().rstrip().split())
visited = [-1] * (max(n, m) * 2 + 1) #๋๋ฐฐ๊น์ง ์ด๋ํ ์ ์๊ธฐ ๋๋ฌธ
cur = n # ์๋น ํ์ฌ์์น
dx = [1, -1, 2]
result=bfs(cur, m)
print(result)
์๋น์ด๋ 1์ด๋์ 3๊ฐ์ง์ ๊ฒฝ์ฐ๋ก ์ด๋ํ ์ ์๊ณ , ๋์์ ์์น๊น์ง ๋๋ฌํ๋ ๊ฐ์ฅ ๋น ๋ฅธ ์๊ฐ์ ๊ตฌํ๋ ๋ฌธ์ ์ธ๋ฐ, ์ด๋ ์ต๋จ๊ฑฐ๋ฆฌ ๊ตฌํ๋ ๋ฐฉ์์ ์ฌ์ฉํ๋ฉด๋๋ค. 3๊ฐ์ง ๋ฐฉํฅ์ผ๋ก ์์ฐจ์ ์ผ๋ก ํ์ํด ๋๊ฐ๊ฒ์ด๊ธฐ ๋๋ฌธ์ BFS๊ฐ ์ ์ ํ ๋ฐฉ๋ฒ์ด๊ณ , visited ๋ฆฌ์คํธ์ ์ด๋ํด์จ ๊ฑฐ๋ฆฌ๊ฐ ์๋ ์๊ฐ์ ์ ์ฅํด๋๋ค.
โ๏ธ์ด๋์๊ฐ์ ์ ์ฅํ๋ visited ๋ฆฌ์คํธ์ ๊ธธ์ด๊ฐ ์ค๋ต์ ์์ธ์ด์๋ค.
max๊ฐ์ ์ขํ ์์น์์ 2๋ฐฐ๋ฅผ ์ด๋ํ๋ค๋ฉด, ์ด ๊ฐ์ด ์ต๋๋ก ์ด๋ํ ์ ์๋ x์ขํ์ด๊ธฐ ๋๋ฌธ์ ์ต์ํ ์ด๊ฐ ๊น์ง ํฌํจํ visited ๋ฆฌ์คํธ๋ฅผ ์์ฑํด์ค์ผ ํ๋ค. ๋ค๋ฅธ ํ์ด๋ฅผ ์ฐธ๊ณ ํด๋ณด๋ ์ฃผ๋ก ๋ฌธ์ ์กฐ๊ฑด์์ ์ฃผ์ด์ง N๊ฐ์ ๋ฒ์๋ฅผ ์ฌ์ฉํ์๋ค.
'๋ฐฑ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-Python] ํ์๋จธ์ : 1440๋ฒ (0) | 2024.06.12 |
---|---|
[๋ฐฑ์ค-Python] ํ์ผ ํฉ์น๊ธฐ 3 : 13975๋ฒ (1) | 2024.06.11 |
[๋ฐฑ์ค-Python] ๋์ดํธ์ ์ด๋ : 7562๋ฒ (0) | 2024.06.10 |
[๋ฐฑ์ค-Python] ์ด์๊ณ์ฐ : 2644๋ฒ (0) | 2024.06.10 |
[๋ฐฑ์ค-Python] ๊ฒ์ : 1072๋ฒ (0) | 2024.06.08 |