3055번: 탈출
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제
www.acmicpc.net
📝 풀이
- 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.
- 물이 차 있는 곳 먼저 각각 큐에 저장하고 BFS를 수행하기 직전에 고슴도치의 위치를 큐에 저장함으로써 물이 먼저 확장되고 나서 고슴도치가 이동하는 식으로 구현
- 큐에는 (y좌표, x좌표, 타입, 시간) 값이 들어감
- 타입 값은 현재 이동중인 개체(고슴도치 또는 물)를 나타냄
- 시간 값은 현재 좌표까지 이동하는데 걸리는 시간을 나타냄
💻 소스코드
import sys
from collections import deque
input = sys.stdin.readline
dy = (1, -1, 0, 0)
dx = (0, 0, 1, -1)
def bfs(start_y, start_x):
que.append((start_y, start_x, 'S', 0))
visited[start_y][start_x] = True
while que:
y, x, type, time = que.popleft()
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if not 0 <= ny < r or not 0 <= nx < c:
continue
if graph[ny][nx] == '.' and not visited[ny][nx]:
visited[ny][nx] = True
que.append((ny, nx, type, time + 1))
elif graph[ny][nx] == 'D' and type == 'S':
return time + 1
return "KAKTUS"
r, c = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(r)]
visited = [[False] * c for _ in range(r)]
que = deque()
start_y = start_x = 0
for i in range(r):
for j in range(c):
if graph[i][j] == 'S':
start_y, start_x = i, j
elif graph[i][j] == '*':
que.append((i, j, '*', 0))
print(bfs(start_y, start_x))
'🥇 Problem Solving > Breadth-First Search' 카테고리의 다른 글
[Python] BOJ / 16234번 / 인구 이동 (0) | 2022.05.31 |
---|---|
[Python] BOJ / 13460번 / 구슬 탈출 2 (0) | 2022.05.16 |
[Python] BOJ / 2206번 / 벽 부수고 이동하기 (0) | 2022.04.30 |
[Python] BOJ / 7569번 / 토마토 (0) | 2022.04.18 |
[Python] BOJ / 10026번 / 적록색약 (0) | 2022.04.18 |