BFS + 구현

구슬탈출

BFS 문제에 구현이 첨가된 문제입니다. 놓치면 안되는 조건들이 많아서 세심하게 구현해야 합니다.

1. 빨간 구슬과 파란구슬은 중력을 이용해 움직임 -> 한칸씩 가는 것이 아니라 끝까지 간다는 뜻(벽, 구멍을 만날 때까지)
   -> 계속 움직이다가 다음 칸이 벽이면 한칸 뒤로가서 멈춤, 구멍이면 멈춤
2. 파란 구슬이 들어가거나, 동시에 들어가면 실패 (파란 구슬이 구멍에 들어갔을 때 무시 )
3. 구슬은 동시에 움직임
4. 동시에 같은 칸에 있을 수 없음 (같은 칸에 있다고 가정하면 더 많이 움직인 구슬이 더 뒤에 있었으므로 뒤로 한 칸 이동)
   5. 방문 배열
5. 10번 이상이면 0 , 빨간 구슬이 구멍에 들어가면 1

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for i in range(n):
	graph.append(list(sys.stdin.readline().rstrip()))
dx =[-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(rx, ry, bx, by, cnt):
	cnt = 0
	visited[rx][ry][bx][by] = True
	while q:
   		 # 구슬이 아래로 이동해도 좌, 우로 또 움직일 수도있다.
		for _ in range(len(q)):
			rx, ry, bx, by, cnt = q.popleft()
            		# 10회 이상 이동하면 종료
			if cnt > 10:
				return 0
               		# 빨간 구슬이 구멍에 들어가면 종료
			if graph[rx][ry] =='O':
				return 1
			# 네 방향으로 움직임 
			for i in range(4):
				rnx = rx
				rny = ry
				bnx = bx
				bny = by
				while True:
					rnx += dx[i]
					rny += dy[i]
                    			# 계속 움직이다가 벽 만나면 뒤로 한칸 이동(빈칸에 있자)
					if graph[rnx][rny]=='#':
						rnx -= dx[i]
						rny -= dy[i]
						break
                        		# 구멍 만나면 그만 가자
					if graph[rnx][rny] == 'O':
						break
                        	# 파란구슬도 마찬가지
                        	while True:
					bnx += dx[i]
					bny += dy[i]
					if graph[bnx][bny]=='#':
						bnx -= dx[i]
						bny -= dy[i]
						break
					if graph[bnx][bny] == 'O':
						break
                        	# 근데 파란 구슬은 구멍에 들어가면 안되니까 무시 
				if graph[bnx][bny] == 'O':
					continue
                    		#  동시에 같은 칸에 있을 수 없음 (같은 칸에 있다고 가정하면 더 많이 움직인 구슬이 더 뒤에 있었으므로 뒤로 한 칸 이동)
				if rnx == bnx and rny == bny:
					if abs(rnx - rx) + abs(rny - ry) > abs(bnx - bx) + abs(bny - by):
						rnx -= dx[i]
						rny -= dy[i]
					else:
						bnx -= dx[i]
						bny -= dy[i]
                        	# 큐에 넣어줌
				if not visited[rnx][rny][bnx][bny]:
					visited[rnx][rny][bnx][bny] = True
					q.append((rnx, rny, bnx, bny, cnt+1))

	return 0
red = []
blue = []
for i in range(n):
	for j in range(m):
		if graph[i][j] == 'R':
			red.append((i, j))
		if graph[i][j] == 'B':
			blue.append((i, j))
q = deque()
q.append((red[0][0], red[0][1], blue[0][0], blue[0][1], 0))
visited = [[[[False for _ in range(m)]for _ in range(n)]for _ in range(m)]for _ in range(n)]
print(bfs(red[0][0], red[0][1], blue[0][0], blue[0][1], 0))