[Python] BOJ 3055 - 탈출(SLIKAR)

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

3055번: 탈출

# 꽤 까다로운 BFS 문제이다.

 

# 이 문제를 푸는데 있어서 주의할 점은

  다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없으므로 물을 먼저 흘려보낸 뒤

  고슴도치를 이동시켜야 한다는 것이다.

 

# dist_beaver는 고슴도치가 이동하는데 걸리는 시간, dist_water는 물이 차는데 걸리는 시간

   두 가지 배열로 상태를 나타내고 비교했다.

 

# bfs_water함수를 통해 먼저 물을 흘려보낸 뒤, bfs_beaver함수로 고슴도치를 이동시킨다.

  bfs_beaver함수에서 dist_beaver[x][y] + 1이 dist_water[nx][ny]보다 작으면 고슴도치가 이동할 때까지

  물이 차지 않는 칸이므로 이동해도 된다.

  (dist_water[nx][ny] == -1이면 물이 아예 안 차므로 역시 이동해도 된다.)

 

# bfs_beaver함수까지 다 실행한 뒤, 목적지인 (end[0], end[1])좌표의 dist값이 -1이면 고슴도치가

   가지 못했으므로 "KAKTUS"를 출력하고 아니면 목적지까지 걸린 시간 + 1을 출력해준다.

 

import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int,input().split())
m = [list(input().rstrip()) for _ in range(R)]
dx, dy = [0,0,-1,1], [-1,1,0,0]
q = deque()
water = []
for i in range(R):
	for j in range(C):
		# start = 고슴도치 시작좌표, water = 물이 있는 초기위치, end = 비버의 집 좌표
		if m[i][j] == 'S':
			start = [i, j]
		elif m[i][j] == '*':
			water.append([i, j])
		elif m[i][j] == 'D':
			end = [i, j]

# 물 흘려보내기
def bfs_water(w):
	for i in w:
		q.append((i[0], i[1]))
	while q:
		x, y = q.popleft()
		for i in range(4):
			nx, ny = x + dx[i], y + dy[i]
			if 0 <= nx < R and 0 <= ny < C and dist_water[nx][ny] == -1 and m[nx][ny] in '.S':
				q.append((nx, ny))
				dist_water[nx][ny] = dist_water[x][y] + 1

# 고슴도치 이동시키기
def bfs_beaver(i, j, dist_water):
	q.append((i, j))
	while q:
		x, y = q.popleft()
		for i in range(4):
			nx, ny = x + dx[i], y + dy[i]
			if 0 <= nx < R and 0 <= ny < C:
				if dist_beaver[nx][ny] == -1 and m[nx][ny] == '.' and (dist_beaver[x][y] + 1 < dist_water[nx][ny] or dist_water[nx][ny] == -1):
					q.append((nx, ny))
					dist_beaver[nx][ny] = dist_beaver[x][y] + 1
				elif m[nx][ny] == 'D':
					dist_beaver[nx][ny] = dist_beaver[x][y] + 1
					return

# 물 먼저 흘려보낸뒤 고슴도치를 이동시켜야 한다!
dist_water = [[-1] * C for _ in range(R)]
bfs_water(water)
dist_beaver = [[-1] * C for _ in range(R)]
bfs_beaver(start[0], start[1], dist_water)

if dist_beaver[end[0]][end[1]] == -1:
	print("KAKTUS")
else:
	print(dist_beaver[end[0]][end[1]] + 1)

(solved.ac 티어: 골드 4)