๐ ๊ณต๋ถํ๋ ์ง์ง์ํ์นด๋ ์ฒ์์ด์ง?
[BAEKJOON python] 5014_์คํํธ๋งํฌ ๋ณธ๋ฌธ
728x90
๋ฐ์ํ
์ค๋์ ๊ฐํธ์ ๋ฉด์ ๋ ์ด๋ค.
๋ฆ์ ์ ์ ๊ฐํธ๋ ์คํํธ๋งํฌ๊ฐ ์๋ ๊ฑด๋ฌผ์ ๋ฆ๊ฒ ๋์ฐฉํ๊ณ ๋ง์๋ค.
์คํํธ๋งํฌ๋ ์ด F์ธต์ผ๋ก ์ด๋ฃจ์ด์ง ๊ณ ์ธต ๊ฑด๋ฌผ์ ์ฌ๋ฌด์ค์ด ์๊ณ ,
์คํํธ๋งํฌ๊ฐ ์๋ ๊ณณ์ ์์น๋ G์ธต์ด๋ค.
๊ฐํธ๊ฐ ์ง๊ธ ์๋ ๊ณณ์ S์ธต์ด๊ณ , ์ด์ ์๋ฆฌ๋ฒ ์ดํฐ๋ฅผ ํ๊ณ G์ธต์ผ๋ก ์ด๋ํ๋ ค๊ณ ํ๋ค.
๋ณดํต ์๋ฆฌ๋ฒ ์ดํฐ์๋ ์ด๋ค ์ธต์ผ๋ก ์ด๋ํ ์ ์๋ ๋ฒํผ์ด ์์ง๋ง,
๊ฐํธ๊ฐ ํ ์๋ฆฌ๋ฒ ์ดํฐ๋ ๋ฒํผ์ด 2๊ฐ๋ฐ์ ์๋ค.
U๋ฒํผ์ ์๋ก U์ธต์ ๊ฐ๋ ๋ฒํผ, D๋ฒํผ์ ์๋๋ก D์ธต์ ๊ฐ๋ ๋ฒํผ์ด๋ค.
(๋ง์ฝ, U์ธต ์, ๋๋ D์ธต ์๋์ ํด๋นํ๋ ์ธต์ด ์์ ๋๋, ์๋ฆฌ๋ฒ ์ดํฐ๋ ์์ง์ด์ง ์๋๋ค)
๊ฐํธ๊ฐ G์ธต์ ๋์ฐฉํ๋ ค๋ฉด, ๋ฒํผ์ ์ ์ด๋ ๋ช ๋ฒ ๋๋ฌ์ผ ํ๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ
์๋ฆฌ๋ฒ ์ดํฐ๋ฅผ ์ด์ฉํด์ G์ธต์ ๊ฐ ์ ์๋ค๋ฉด, "use the stairs"๋ฅผ ์ถ๋ ฅํ๋ค.
์ฒซ์งธ ์ค์ F, S, G, U, D๊ฐ ์ฃผ์ด์ง๋ค.
(1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) ๊ฑด๋ฌผ์ 1์ธต๋ถํฐ ์์ํ๊ณ ,
๊ฐ์ฅ ๋์ ์ธต์ F์ธต์ด๋ค.
์ฒซ์งธ ์ค์ ๊ฐํธ๊ฐ S์ธต์์ G์ธต์ผ๋ก ๊ฐ๊ธฐ ์ํด ๋๋ฌ์ผ ํ๋ ๋ฒํผ์ ์์ ์ต์๊ฐ์ ์ถ๋ ฅ
๋ง์ฝ, ์๋ฆฌ๋ฒ ์ดํฐ๋ก ์ด๋ํ ์ ์์ ๋๋ "use the stairs"๋ฅผ ์ถ๋ ฅ
# 1) BFS
from collections import deque
# ๊ฑด๋ฌผ๋์ด, ๊ฐํธ์์น, ์ฌ๋ฌด์ค์์น, ์ฌ๋ผ๊ฐ์ผ๋๋ ์ธต, ๋ด๋ ค๊ฐ์ผ๋๋ ์ธต
F, S, G, U, D = map(int, input().split())
def bfs(s, g) :
visited = [-1] * (F + 1)
# ํ์ฌ ๊ฐํธ ์์น
q = deque([s])
visited[s] = 0
while q :
x = q.popleft()
# ์ฌ๋ฌด์ค์ ๋์ฐฉ
if x == g :
return visited[x]
UP = x + U
DOWN = x - D
if (UP <= F) and (visited[UP] == -1) :
q.append(UP)
visited[UP] = visited[x] + 1
if (DOWN > 0) and (visited[DOWN] == -1) :
q.append(DOWN)
visited[DOWN] = visited[x] + 1
return "use the stairs"
print(bfs(S, G))
# input
# 10 1 10 2 1
# output
# 6
# input
# 100 2 1 1 0
# output
# use the staris
728x90
๋ฐ์ํ
'๐ฆฅ ์ฝํ > BAEKJOON' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BAEKJOON python] 14503_๋ก๋ด ์ฒญ์๊ธฐ (0) | 2022.10.09 |
---|---|
[BAEKJOON python] 2573_๋น์ฐ (0) | 2022.10.08 |
[BAEKJOON python] 7569_ํ ๋งํ (0) | 2022.10.08 |
[BAEKJOON python] 9205_๋งฅ์ฃผ ๋ง์๋ฉด์ ๊ฑธ์ด๊ฐ๊ธฐ (0) | 2022.10.08 |
[BAEKJOON python] 2468_์์ ์์ญ (1) | 2022.10.08 |
Comments