[백준/파이썬] 16954번 움직이는 미로 탈출

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

16954번: 움직이는 미로 탈출

 

문제 해석

 

가장 좌측, 가장 아래에 위치한 욱제의 캐릭터가 가장 우측 위쪽으로 이동할 수 있는지 구하는 문제이다.

이때 욱제의 이동 경우는 제자리, 상하좌우 대각선이다.

벽이 존재하며 벽은 욱제가 이동한 뒤에 한칸 씩 떨어진다.

........ ........
........ ........
........ ........
........ ........
#....... ........
.####### #.......
#....... .#######
........ #.......

해당 경우 처럼 1칸씩 떨어지며 맨 위의 행은 빈칸으로 남는다.

---

코드

 

from collections import deque
input = __import__('sys').stdin.readline

arr = []
wall = []

# Input
for i in range(8):
	arr.append(list(input().strip()))
	for j in range(8):
		if arr[i][j] == '#': wall.append((i, j))

dx, dy = [-1, 1, 0, 0, -1, -1, 1, 1, 0], [0, 0, -1, 1, -1, 1, -1, 1, 0]

def moveWall(wall): # 벽이 모두 한칸씩 떨어짐
	temp = []
	for i, j in wall:
		arr[i][j] = '.'
	
	for i, j in wall:
		x, y = i + 1, j
		if x >= 8: continue
		temp.append((x, y))
		arr[x][y] = '#'

	return temp

def bfs(x, y, wall):
	visit = [[0] * 8 for _ in range(8)]
	q = deque()
	q.append((x, y))

	while q:
		# 한 사이클이 끝나면 벽이 떨어져야함.
		if not wall:	# 벽이 없는 경우는 갈 수 있음.
			return 1
		for _ in range(len(q)):
			i, j = q.popleft()
			if arr[i][j] == '#': continue	# 내 위치에 벽이 내려온 경우
			for k in range(9):
				x, y = i + dx[k], j + dy[k]
				if not(0 <= x < 8 and 0 <= y < 8): continue
				if arr[x][y] == '.' and visit[x][y] == 0:
					if x == 0 and y == 7: return 1	# 목표에 도착한 경우
					q.append((x, y))
					visit[x][y] = 1
					
		# 벽 내려오기
		wall = moveWall(wall)
		visit = [[0] * 8 for _ in range(8)]
		
	return 0

# 초기 위치 7, 0
print(bfs(7, 0, wall))

---

문제 풀이

 

너비 우선 탐색으로 한 사이클이 종료 시 벽이 떨어지도록 구현해야 한다.

벽이 떨어졌다면 방문 노드 또한 초기화 시켜 벽이 모두 떨어져야만 갈 수 있는 경우도 생각해야 한다.