๋ฌธ์
๊ฐ ์ ์๋ ๋ฐฉํฅ์ด ๋ ๋ฐฉํฅ๋ง ์กด์ฌํ๋ BFS ๋ฌธ์ ์์ต๋๋ค.
-
์ BFS์ธ๊ฐ? : ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ๋ ๋ฌธ์ ์๊ธฐ ๋๋ฌธ์ ๋๋ค. ํ ๋ ธ๋์์ ๊ฐ ์ ์๋ ํ ๊ฐ์ ๊ธธ์ ๋๊น์ง ํ๊ณ ๋๋ DFS์ ๋ฌ๋ฆฌ, BFS๋ ํ ๋ ธ๋์์ ๊ฐ ์ ์๋ ๋ชจ๋ ๊ธธ๋ค์ ํ๋์ฉ ์ํํ๋ฉฐ ์งํํ๊ธฐ ๋๋ฌธ์, ๊ฐ์ฅ ๋จผ์ Goal์ ๋์ฐฉํ๋ ๋ฃจํธ๊ฐ ์ต๋จ๊ฑฐ๋ฆฌ์์ ์ ์ ์์ต๋๋ค.
- ์๊ฐ ์์ ๊ฐ๊ฑฐ๋ผ๋ ํ์ ์ด ์์๋์? : ๋ค. ์ต๋ Final ์ธต์ด 10^6์ธต์ด๊ณ , ์ต์ ์ ๊ฒฝ์ฐ๋๋ผ๋ visited ๋ฐฐ์ด์ ๋ชจ๋ ๋ ธ๋๋ฅผ ๋ค ๋ฐฉ๋ฌธํด๋ณด๋ ๊ฒ์ผ๋ก ๋๋๊ธฐ ๋๋ฌธ์ 10^6์ด ๊ฑธ๋ฆฝ๋๋ค. bfs ์์์ ์ ์ ํ๊ฒ ์ฒ๋ฆฌ๋ง ํด์ฃผ๊ณ ์๋ค๋ฉด, ์ด๋ก ์ O(N)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ต๋๋ค.
- ๊ณต๊ฐ๋ณต์ก๋๋ฅผ ์ด๊ณผํ์ง ์์๋์ง? : ์๊ทธ๋ด๊ฑฐ๋ผ ์๊ฐํ์ต๋๋ค. 256MB๋ก ๋ฉ๋ชจ๋ฆฌ์ ํ์ด ๋๋ํ ํธ์ด์๊ธฐ ๋๋ฌธ์ ๋๋ค. ํ์ด์ฌ์ ๋ฐ์ดํฐํ์ ๋ณ ํฌ๊ธฐ๊ฐ ์ ํํ ์ด๋ป๊ฒ ๋๋์ง๋ ํ์ ํ ์ ์์์ง๋ง, ๋๋ต boolean์ ๋๋ํ 1๋ฐ์ดํธ๋ก ์๊ฐํ๋๋ผ๋ 10^6(MB) ์ง๋ฆฌ ๋ฐฐ์ด์ 256๊ฐ ๋ง๋ค ์ ์๋ ์์ด๊ธฐ ๋๋ฌธ์ ๋๋ค.
์ฒซ ์๋ : ์๊ฐ์ด๊ณผ
์ ๊ฐ ํ๋ ธ๋ ๋ถ๋ถ์ ์ด๋์์ ๋ฐฉ๋ฌธ์ ๊ธฐ๋กํด์ผ ํ๋๊ฐ?์ ๋ถ๋ถ์ด์์ต๋๋ค. ๋ฐฉ๋ฌธํ ๋ ธ๋๋ค์ ์์๋๋ก ๊ฐ๊ณ ์๋ queue์ ๋ฃ์ผ๋ฉด์ ๋์์ ๋ฐฉ๋ฌธ ๊ธฐ๋ก๊น์ง ํด์ฃผ์ด์ผ ํ๋๋ฐ, ๋ ธ๋๋ฅผ ๊บผ๋ด๋ ์์ ์์ ๋ฐฉ๋ฌธ ๊ธฐ๋ก์ ํด์ฃผ์ด์ ์๊ฐ์ด๊ณผ๊ฐ ๋์์ต๋๋ค.
BFS์์๋ ํ๋ฅผ ์ฌ์ฉํ๋ ๊น๋ญ์ ์ ์ ์ ์ถ๋ก ๋ ธ๋๊ฐ pop๋๊ฒ ๋ฉ๋๋ค. ์ต์ด์ ๋ฐฉ๋ฌธ ๊ธฐ๋ก์ ๋ฃ์ด์ฃผ๋ ๊ฒฝ์ฐ์๋, ์ด์ ๋ฐ๋ผ ๋ค์๊ณผ ๊ฐ์ ์์๋ก push ์ดํ pop์ ๊ธฐ๋ค๋ฆฌ๊ฒ ๋ฉ๋๋ค.
- ํ์ ๊ฐ์ฅ ๋๋จ์ push ๋๋ค.
- ์์ ๋ ธ๋๋ค์ด ๋ชจ๋ pop๋ ๋๊น์ง ๊ธฐ๋ค๋ฆฐ๋ค.
- ์์ ์ ์ฐจ๋ก๊ฐ ์ค๋ฉด pop๋๋ค.
๊ทธ๋ ๊ธฐ ๋๋ฌธ์, pop๋ ๋ ๋ฐฉ๋ฌธ๊ธฐ๋ก์ ํด์ค๋ค๋ ๊ฒ์ (1) pop๋๊ธฐ๊น์ง ์ฐจ๋ก๋ฅผ ๊ธฐ๋ค๋ฆฌ๋ ๋ชจ๋ ๋ ธ๋๋ค (2) ์์ ์ด push๋ ํ, pop๋๊ธฐ ์ ๊น์ง ๋ค์ด์จ ๋ชจ๋ ๋ ธ๋๋ค ๊ณผ์ ์ค๋ณต์ด ํ์ฉ๋ฉ๋๋ค. ์ด์ ๋ฐ๋ผ ๋น์ฐํ ์๊ฐ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ ๊ฒ์ด๊ณ ์.
์ด๋ฌํ ์๊ณ ๋ฆฌ์ฆ์ ๋นํจ์จ์ฑ์ ๊ณ ์น ์ ๋ต ์ฝ๋๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์ ๋ต์ฝ๋
# 5014
import sys
from collections import deque
Final, Start, Goal, Up, Down = map(int, input().split())
visited = [False]*(Final+1)
moves = [Up, Down*(-1)]
def bfs(start) :
visited[start]=True
cnt = 0
queue = deque([(start,cnt)])
while queue : # O(N)
n, cnt = queue.popleft() # O(1)
# visited[n] = True
if(n == Goal) :
return cnt
for dn in moves : # O(2)
next = n + dn
if (next <= Final) and (next > 0) and (visited[next] == False) :
queue.append((next,cnt+1)) # O(1)
visited[next] = True
return "use the stairs"
print(bfs(Start))
๊ฐ์ ๋ณ๋์ด ์์ ๊ฒ์ด๊ณ , ์์ด์ผํ๊ธฐ ๋๋ฌธ์ tuple์ ์ฌ์ฉํด deque ๋ฆฌ์คํธ์ ์ญ ๋ฃ์์ต๋๋ค. ํํ๋ก ๋ฌถ์ด๋ ๊ฒ์ ํ์ฌ ๋ ธ๋์ ๋ฒํธ(=ํ์ฌ ์ดํด๋ณด๋ ์ธต์)์ ๋ช ๋ฒ ์์ง์๋์ง๋ฅผ ์ธ๋ cnt ๋ณ์์ ๋๋ค.
์๋กญ๊ฒ ์๊ฒ๋ ์
n, cnt = queue.popleft()
๋ฅผ ์ฌ์ฉํด ํ ๋ฒ์ ํ๋ผ๋ฏธํฐ๋ฅผ ๋ฐ์ ์ ์๋ค.- ๋ฐฉ๋ฌธ ๊ธฐ๋ก์ ์ด๋์์ ํ๋ ์ง๋ ์ ๊ฒฝ์จ์ฃผ์ด์ผ ํ๋ค.
- ํ์ด์ฌ์ ๋ฆฌํด๊ฐ์ ๋ฐ์ดํฐํ์ ์ด ๋ฌ๋ผ๋ ์๊ด์๋ค! (n==Goal์ธ ๊ฒฝ์ฐ์๋ Integer์ธ cnt๋ฅผ, while์ ๋ชจ๋ ๋์์ผ๋ Goal์ ์ฐพ์ง ๋ชปํ ๊ฒฝ์ฐ์๋ str์ ๋ฐํํด์ฃผ๊ณ ์๋ค.)
๊ฐ์ธ์ ์ผ๋ก ์์๊ฒ ์ง์ง ์ฝ๋๋ผ๊ณ ์๊ฐํฉ๋๋ค. ์ ๊ธฐ์์ ์กฐ๊ธ ๋ ์ด์๊ฒ ํ๋ ค๋ฉด, isValidMove ๋ผ๋ ์ด๋ฆ์ ํจ์๋ฅผ ๋ง๋ค์ด์ (next <= Final) and (next>0)
์ ๊ฐ๋
์ฑ์ ๋์ผ ์ ์๊ฒ ์ผ๋, ์ฒ์์ ์๊ฐ์ด๊ณผ๊ฐ ๋๋ฉด์ ํจ์๋ฅผ ํ๊ณ ๋ค์ด๊ฐ๋ ์๊ฐ์ด๋ผ๋ ์์ ๋ณด๋ ค๊ณ ํ์ด ์ผ๋ ๋ถ๋ถ์
๋๋ค.. ใ
ใ
ใ