# BOJ - 3055 - 탈출

Updated:

``````import sys
from collections import deque

def BFS(dq, Map, N, M):
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

Q = deque()
while dq:
x, y = dq.pop()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]

if 0 <= nx < N and 0 <= ny < M:
if Map[x][y] == '*':
if Map[nx][ny] == "." or Map[nx][ny] == "S":
Map[nx][ny] = "*"
Q.append((nx, ny))
elif Map[x][y] == "S":
if Map[nx][ny] == ".":
Map[nx][ny] = "S"
Q.append((nx, ny))

elif Map[nx][ny] == "D":
return True
return Q

def solution():
Map = []
start = deque()
water = deque()

for _ in range(R):

for i in range(R):
for j in range(C):
if Map[i][j] == 'S':
start.append((i, j))
elif Map[i][j] == 'D':
end = [(i, j)]
elif Map[i][j] == '*':
water.append((i, j))

time = 0
while True:
time += 1
start = BFS(start, Map, R, C)
water = BFS(water, Map, R, C)

if start == True:
print(time)
break
elif not start:
print("KAKTUS")
break

temp = []
for x, y in start:
if Map[x][y] == 'S':
temp.append((x, y))
start = temp

solution()
``````

https://www.acmicpc.net/problem/3055

Categories:

Updated: