[๋ฐฑ์ค-16928] ๋ฑ๊ณผ ์ฌ๋ค๋ฆฌ ๊ฒ์
๐ Problem Solving/Baekjoon
import sys
from collections import deque
distance = [-1] * 101
def bfs(x):
queue = deque()
queue.append(x)
distance[x] = 0
while queue:
x = queue.popleft()
for i in range(1, 7):
nx = x + i
if nx > 100:
continue
if graph[nx]:
if (
distance[graph[nx][0]] == -1
or distance[graph[nx][0]] > distance[x] + 1
):
distance[graph[nx][0]] = distance[x] + 1
queue.append(graph[nx][0])
else:
if distance[nx] == -1 or distance[nx] > distance[x] + 1:
distance[nx] = distance[x] + 1
queue.append(nx)
graph = [[] for _ in range(101)]
n, m = map(int, sys.stdin.readline().split())
for _ in range(n):
x, y = map(int, sys.stdin.readline().split())
graph[x].append(y)
for _ in range(m):
u, v = map(int, sys.stdin.readline().split())
graph[u].append(v)
bfs(1)
print(distance[-1])
ํด์ค
bfs๋ก ํด๊ฒฐํ ์ ์๋ ๋ฌธ์ ์๋ค. ์ฌ๋ค๋ฆฌ๋ ๋ฑ์ด ์์นํ ๊ณณ์ ์ฃผ์ด์ง ์ขํ๋ก ์ด๋ ํ, ์ถ๋ฐ ๊ฐ์ 1์ ๋ํด์ฃผ๋ฉด ๋๋ค.
'๐ Problem Solving > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-18870] ์ขํ ์์ถ / Python (0) | 2021.05.28 |
---|---|
[๋ฐฑ์ค-17219] ๋น๋ฐ๋ฒํธ ์ฐพ๊ธฐ / Python (0) | 2021.05.28 |
[๋ฐฑ์ค-11723] ์งํฉ / Python (0) | 2021.05.28 |
[๋ฐฑ์ค-11659] ๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ4 / Python (0) | 2021.05.27 |
[๋ฐฑ์ค-11286] ์ ๋๊ฐ ํ / Python (0) | 2021.05.27 |