BFS + 구현

구슬탈출3

구슬탈출
구슬탈출2
문제와 거의 동일하지만 방향정보를 넣어주어야 합니다. 예를 들어서 아래 -왼 /아래 -오 이렇게 두갈래길로 갈 수 있다고 하면 DL DR 이겠죠?
이렇게 방향 정보를 모두 기록한 후에 빨간 구슬이 구멍에 들어올 때의 방향 정보만을 출력하면 됩니다.

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]
moveTypes =['U','D','L','R']
def bfs(rx, ry, bx, by, cnt,d):
	cnt = 0
	visited[rx][ry][bx][by] = True
	while q:
		for j in range(len(q)):
			rx, ry, bx, by, cnt, d = q.popleft()
			if cnt > 10:
				print(-1)
				return
                	# 갯수와 길 정보 출력
			if graph[rx][ry] =='O':
				print(cnt)
				print(d)
				return

			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, d + moveTypes[i]))
	print(-1)
	return
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)]
bfs(red[0][0], red[0][1], blue[0][0], blue[0][1], 0, '')```