
▶ 골드 5 (BFS)

풀이
길을 이동하는 방법은 1) 뒤로 가기 2) 앞으로 가기 3) 옆으로 가기
BFS를 통해서 갈 수 있는 모든 경로를 방문한 후, N칸이 넘어가면 성공으로 간주하고 1을 출력한 뒤 종료합니다.
갈 수 있는 경로의 조건은
- 현재 시간 번째 칸 이상이고 (뒤로가는 경우만 해당)
- 방문하지 않았고
- 이동할 수 있는 칸인 경우
현재 칸이 N번 째 이상인 경우 종료.
고민한 점
현재 칸에서 이동할 수 있는 3가지 칸에서는 동일한 시간을 가져야하는데,
처음에 visited를 숫자로 저장하여 time을 관리하려고 하니 칸을 이동할 때마다 시간이 증가했습니다.
그래서 queue에 [줄, 인덱스, 방문 시간] 형태로 방문 시간을 추가했습니다.
코드
# 15558 점프 게임
from collections import deque
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
map = [input().strip() for _ in range(2)]
# BFS
queue = deque([(0, 0, 0)])
visited = [[False for _ in range(n)] for _ in range(2)]
while queue:
row, idx, time = queue.popleft()
routes = [[row, idx + 1], [row, idx - 1], [1 - row, idx + k]]
for i in range(len(routes)):
nextRow, nextIdx = routes[i]
if nextIdx >= n:
print(1)
exit()
if time < nextIdx and not visited[nextRow][nextIdx] and map[nextRow][nextIdx] == '1':
visited[nextRow][nextIdx] = True
queue.append([nextRow, nextIdx, time + 1])
print(0)
'Algorithm > Baekjoon' 카테고리의 다른 글
14502_연구소 (0) | 2025.03.07 |
---|---|
11123_양 한마리... 양 두마리... (0) | 2025.03.07 |
16719_ZOAC (0) | 2025.02.25 |
5014_스타트링크 (0) | 2025.02.25 |
16935_배열 돌리기3 (2) | 2025.02.24 |