[Python] BOJ 6593 - Dungeon Master(상범 빌딩)

www.acmicpc.net/problem/6593

6593번: 상범 빌딩

 

이제는 무난한(?) BFS문제이다. 단지 3차원배열을 사용해 조금 귀찮을 뿐이다.

1. Test Case마다 m(빌딩상태), time(이동시간), visited(방문여부) 배열을 초기화해주고 m을 입력받는다.

 

2. m을 전체돌면서 'S'가 있는 칸의 좌표를 sz, sx, sy에 저장하고, 'E'가 있는 칸의 좌표를 ez, ex, ey에 저장한다.

 

3. bfs를 돌리면서 다음 칸으로 갈때마다 시간을 1씩 더해주고 큐에 넣고 방문처리를 해준다.

 

4. 도착지점의 시간인 m[ez][ex][ey]가 존재한다면 탈출을 할 수 있으므로 시간을 출력하고 아니면 Trapped!를 출력한다.

 

 

 

from collections import deque
import sys
input = sys.stdin.readline
dx, dy, dz = [-1,1,0,0,0,0], [0,0,-1,1,0,0], [0,0,0,0,-1,1]
def bfs():
	q = deque()
	q.append([sz, sx, sy])
	visited[sz][sx][sy] = True
	while q:
		z, x, y = q.popleft()
		for i in range(6):
			nz, nx, ny = z + dz[i], x + dx[i], y + dy[i]
			if 0 <= nz < L and 0 <= nx < R and 0 <= ny < C and not visited[nz][nx][ny]:
				if m[nz][nx][ny] == '.' or m[nz][nx][ny] == 'E':
					time[nz][nx][ny] = time[z][x][y] + 1
					q.append([nz, nx, ny])
					visited[nz][nx][ny] = True

while True:
	L, R, C = map(int,input().split())
	if L == 0:
		break
	else:
		m = [[] * R for _ in range(L)]
		time = [[[0] * C for _ in range(R)] for _ in range(L)]
		visited = [[[False] * C for _ in range(R)] for _ in range(L)]
		for i in range(L):
			for j in range(R):
				m[i].append(list(map(str,input())))
			input()
		for k in range(L):
			for i in range(R):
				for j in range(C):
					if m[k][i][j] == 'S':
						sz, sx, sy = k, i, j
					elif m[k][i][j] == 'E':
						ez, ex, ey = k, i, j
		bfs()
		if time[ez][ex][ey]:
			print("Escaped in " + str(time[ez][ex][ey]) + " minute(s).")
		else:
			print("Trapped!")

(solved.ac 티어: 골드 5)

 

# 이와 비슷한 문제로는 3차원배열을 사용하는 토마토문제가 있다.

www.acmicpc.net/problem/7569

7569번: 토마토