๐ญ ๋ฌธ์ ์ดํด
๊ฐํธ๊ฐ ์๋ฆฌ๋ฒ ์ดํฐ๋ฅผ ํ๊ณ S์ธต์์ G์ธต์ผ๋ก ๊ฐ๊ธฐ ์ํ ์ต์ ์ด๋ ํ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค.
์ด ๋ฌธ์ ์ ํน์ง์ ํ ๋ฒ์ ํ๋์ ๋ฒํผ๋ง ๋๋ฌ Up ๋๋ Down ํฌ๊ธฐ๋งํผ๋ง ์ด๋ํ ์ ์๋ค.
๋๋น ์ฐ์ ํ์์ ์ํํ์ฌ ๋ฌธ์ ๋ฅผ ํ๋ฉด ๋ชฉ์ ์ง๊น์ง ์ต์ ํ์๋ก ์ด๋ํ๊ฒ ํ ์ ์๋ค.
visited ๋ฐฐ์ด์ ๋์ ํ์ฌ cnt ๋ฐฐ์ด์ ์ฌ์ฉํ๋ค.
cnt ๋ฐฐ์ด์ ๊ธฐ๋ณธ๊ฐ์ด -1๋ก ์ด๊ธฐํ๋์ด์๊ณ , ์ถ๋ฐ์ ์ 0์ผ๋ก ์ค์ ์ ํ๋ค.
Up ๋๋ Down ์ ํ์ ํ์ ๋ฃ์ ๋๋ง๋ค cnt ๋ฐฐ์ด์ ๊ทธ ์์น๊ฐ์ ์ด์ ์์น ๊ฐ +1๋ก ์ค์ ํ๋ค.
์ต์ข ๋ชฉ์ ์ง์ธ g๊น์ง ๋์ฐฉํ๋ ์ต์ ์ด๋ ํ์๊ฐ cnt[g]์ ๊ตฌํด์ง๊ฒ ๋๋ค.
๊ตฌํ ์ธ์ด: Python
from collections import deque
def solve():
global total, kangho, up, down, cnt
queue = deque()
queue.append(kangho)
cnt[kangho] = 0
while queue:
now = queue.popleft()
for next in (now + up, now - down):
if 1 <= next <= total:
# ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์ธต
if cnt[next] == -1:
cnt[next] = cnt[now] + 1
queue.append(next)
total, kangho, dest, up, down = map(int, input().split())
cnt = [-1] * (total+1)
solve()
# ์ฌ์ ํ -1์ด๋ผ๋ฉด ๊ทธ ์ธต์ ๊ฐ ์ ์๋ค๋ ๋ป
if cnt[dest] == -1:
print("use the stairs")
else:
print(cnt[dest])
'Problem_Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] ๋ฐฑ์ค 2573 ๋น์ฐ / BFS (0) | 2021.01.14 |
---|---|
[BOJ] ๋ฐฑ์ค 2468 ์์ ์์ญ / BFS (0) | 2021.01.13 |
[BOJ] ๋ฐฑ์ค 13549 ์จ๋ฐ๊ผญ์ง 3 / BFS (0) | 2021.01.12 |
[BOJ] ๋ฐฑ์ค 13913 ์จ๋ฐ๊ผญ์ง 4 / BFS (0) | 2021.01.12 |
[BOJ] ๋ฐฑ์ค 12851 ์จ๋ฐ๊ผญ์ง 2 / BFS (0) | 2021.01.12 |