알고리즘/문제 풀이
[Python/파이썬 3055 백준] 탈출
광규니
2021. 4. 9. 23:03
반응형
3055번: 탈출
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제
www.acmicpc.net
풀이
bfs 문제인데 물의 경로가 고슴도치에 영향을 주는 문제
처음 물(*)을 bfs 돌려서 check_water에 시간을 넣어줬습니다.
이 과정에서 물이 여러 개인 경우랑 두번째 물 bfs 일 경우 시간이 더 적게 걸리는 상황으로 걸러줬습니다.
다음 고슴도치(S) bfs 돌려서
물이 아예 없을 경우와 물보다 빨리 고슴도치가 움직인 경우를 걸러줬습니다.
제출과정에서 계속 10%에서 불통됐는데
반례가
D..
...
..S
이 경우처럼 물이 아예 없을때 틀렸어용...
from collections import deque
import sys
input=sys.stdin.readline
r,c=map(int,input().split())
graph=[list(input().rstrip()) for _ in range(r)]
check_water=[[-1]*c for _ in range(r)]
check=[[-1]*c for _ in range(r)]
dx=[0,0,1,-1]
dy=[1,-1,0,0]
queue=deque()
# 고슴도치 bfs
def bfs(x,y):
queue.append((x,y))
check[x][y]=0
while queue:
x,y=queue.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<r and 0<=ny<c:
if graph[nx][ny]=='.':
# 물이 없는경우
if check[nx][ny]==-1 and check_water[nx][ny]==-1:
check[nx][ny]=check[x][y]+1
queue.append((nx,ny))
# 물이 먼저 흐른경우 물의 경로보다 더 작은경우만 +1
elif check[nx][ny]==-1 and check_water[nx][ny]>check[x][y]+1:
check[nx][ny]=check[x][y]+1
queue.append((nx,ny))
# 최종 목적지
elif graph[nx][ny]=='D' and check[nx][ny]==-1:
check[nx][ny]=check[x][y]+1
print(check[final_x][final_y] if check[final_x][final_y]!=-1 else 'KAKTUS')
# 물의 bfs
def bfs_water(x,y):
queue.append((x,y))
check_water[x][y]=0
while queue:
x,y=queue.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<r and 0<=ny<c:
if graph[nx][ny]=='.' or graph[nx][ny]=='S':
# 물이 여러개인경우 고려
# 처음 물의 경로를 구할 때
if check_water[nx][ny]==-1:
check_water[nx][ny]=check_water[x][y]+1
queue.append((nx,ny))
# 물이 두개 이상일 때
else:
if check_water[nx][ny]>check_water[x][y]+1:
check_water[nx][ny]=check_water[x][y]+1
queue.append((nx,ny))
for i in range(r):
for j in range(c):
if graph[i][j]=='S':
start_x,start_y=i,j
elif graph[i][j]=='*':
bfs_water(i,j)
elif graph[i][j]=='D':
final_x,final_y=i,j
bfs(start_x,start_y)반응형