257. 탈출
https://www.acmicpc.net/problem/3055
1) 어떤 전략(알고리즘)으로 해결?
2) 코딩 설명
<내 풀이>
from collections import deque
import sys
r,c = map(int, sys.stdin.readline().rstrip().split())
mapp = []
for rr in range(r) :
mapp.append(list(sys.stdin.readline().rstrip()))
water_map = list([-1 for _ in range(c)] for _ in range(r))
godo_map = list([-1 for _ in range(c)] for _ in range(r))
# 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동
# 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차
# 상하좌우 살펴주고 비버의 소굴(D)로 이동할 수 없
rdir = [-1, 1, 0, 0]
cdir = [0, 0, -1, 1]
# 비어있는 곳은 '.'로 표시되어 있고,
# 물이 차있는 지역은 '*',
# 돌은 'X'로 표시되어 있다.
# 비버의 굴은 'D'로,
# 고슴도치의 위치는 'S'로
water=deque() # 물 위치 담을
for row in range(r) :
for col in range(c) :
if mapp[row][col] == 'S' :
godo = (row,col)
mapp[row][col] = "."
godo_map[row][col] = 0
# 고슴도치 위치는 저장 해놓고 갈 수 있는 . 으로 바꿈
elif mapp[row][col] == '*' :
water.append((row,col))
water_map[row][col] = 0 # 원래부터 물이면 0초 시작 !
elif mapp[row][col] == 'D' :
destination = (row,col)
# water 차오르는 시간 기록
while water :
noww= water.popleft()
wr,wc = noww[0], noww[1]
for i in range(4) :
if 0<=wr+rdir[i]<r and 0<=wc+cdir[i]<c \
and mapp[wr+rdir[i]][wc+cdir[i]] == '.' \
and water_map[wr+rdir[i]][wc+cdir[i]] ==-1 :
water_map[wr+rdir[i]][wc+cdir[i]] = water_map[wr][wc] +1
water.append((wr+rdir[i],wc+cdir[i] ))
# 고슴도치가 갈 수 있는 곳을 waterMap과 비교해 waterMap보다 작으면 갈 수 있게 해줍니다.
# 단, 동시에 물과 고슴도치가 도착하는 경우도 이동할 수 없으므로 +1로 비교해줍니다.
q=deque()
q.append(godo)
while q:
x, y = q.popleft()
for i in range(4):
dx = x + rdir[i]
dy = y + cdir[i]
# 범위, 이동가능, 방문 여부 체크
if 0 <= dx < r and 0 <= dy < c and \
mapp[dx][dy] in '.D' and \
godo_map[dx][dy] == -1 and\
(godo_map[x][y] + 1 < water_map[dx][dy] or water_map[dx][dy] == -1):
# 다음 시간에 물이 찰 곳인지 여부 검사
godo_map[dx][dy] = godo_map[x][y] + 1
q.append([dx, dy])
if godo_map[destination[0]][destination[1]]==-1 :
print('KAKTUS')
else:
print(godo_map[destination[0]][destination[1]])
<다른 분의 풀이 or 내 틀렸던 풀이, 문제점>
메모리초과
from collections import deque
import sys
r,c = map(int, sys.stdin.readline().rstrip().split())
mapp = []
for rr in range(r) :
mapp.append(list(sys.stdin.readline().rstrip()))
# 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동
# 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차
# 상하좌우 살펴주고 비버의 소굴(D)로 이동할 수 없
rdir = [-1, 1, 0, 0]
cdir = [0, 0, -1, 1]
# 비어있는 곳은 '.'로 표시되어 있고,
# 물이 차있는 지역은 '*',
# 돌은 'X'로 표시되어 있다.
# 비버의 굴은 'D'로,
# 고슴도치의 위치는 'S'로
water=[] # 물 위치 담을
for row in range(r) :
for col in range(c) :
if mapp[row][col] == 'S' :
godo = (row,col)
mapp[row][col] = "."
elif mapp[row][col] == '*' :
water.append((row,col))
elif mapp[row][col] == 'D' :
destination = (row,col)
def bfs(startrow, startcol) :
global mini_time
global possible
q = deque()
time=0
curtime = 0
q.append((startrow, startcol, time))
for w in range(len(water)) :
wr, wc = water[w][0], water[w][1]
for i in range(4) :
if 0<=wr+rdir[i]<r and 0<=wc+cdir[i]<c \
and mapp[wr+rdir[i]][wc+cdir[i]] == '.' :
mapp[wr+rdir[i]][wc+cdir[i]] ='*'
# water.append((wr+rdir[i], wc+cdir[i]))
while q :
now = q.popleft()
# 물 먼저 채우고
if now[2] > curtime :
curtime = now[2]
for rrrr in range(r) :
for cccc in range(c) :
if mapp[rrrr][cccc] == "*" :
for i in range(4) :
if 0<=rrrr+rdir[i]<r and 0<=cccc+cdir[i]<c \
and mapp[rrrr+rdir[i]][cccc+cdir[i]] == '.' :
mapp[rrrr+rdir[i]][cccc+cdir[i]] ='*'
water.append((rrrr+rdir[i], cccc+cdir[i]))
# print(now)
# for ma in mapp :
# print(ma)
if now[0]==destination[0] and now[1]==destination[1] :
possible = True
if now[2] < mini_time :
mini_time = now[2]
# 두더지 이동
for j in range(4) :
# print(now[0]+rdir[j] , now[1]+cdir[j])
if (0<=now[0]+rdir[j]<r and 0<=now[1]+cdir[j]<c) \
and \
mapp[now[0]+rdir[j]][now[1]+cdir[j]]!='*' \
and\
(mapp[now[0]+rdir[j]][now[1]+cdir[j]] == '.' or mapp[now[0]+rdir[j]][now[1]+cdir[j]] == 'D') :
q.append((now[0]+rdir[j], now[1]+cdir[j],now[2]+1 ))
mini_time = 1000
possible = False
bfs(godo[0], godo[1])
if possible :
print(mini_time)
else :
print("KAKTUS")
<반성 점>
- 너무 시간 오래걸림
- 치즈랑 비슷한 문젠데 좀 더 빨리 풀자 마니 반복하면 좋을 문제
