🛠 문제
👩🏻💻 해결 방법
우선 빨간 구슬과 파란 구슬의 위치 저장을 위한 4차원 리스트 visit을 만들어주었다
구슬의 현재 위치에서부터 bfs를 적용해주기 위해 for문을 통해 현재 위치를 찾고, q에 넣어주었다
q에서 꺼낸 depth 값이 10 이상이면 break를 해주고, 그렇지 않으면 move 함수를 통해 한쪽 방향으로 기울였을 때 구슬의 위치를 구해주었다
파란 구슬이 'O'위치가 아니면서 빨간 구슬이 'O'위치일 때 depth를 출력해주었다
만약 두 구슬의 위치가 겹쳤을 경우, 더 많이 이동한 구슬을 한 칸 뒤로 이동시켜주는 과정이 필요했다
빨간 구슬의 위치가 'O'이 아닐 경우, 방문 처리를 해주고 q에 depth+1 값을 넣어 bfs를 계속 진행해주었다
소스 코드
from collections import deque
n, m = map(int, input().split())
board = [list(input()) for _ in range(n)]
visit = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = deque()
def init():
rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
for j in range(m):
if board[i][j] == 'R':
rx, ry = i, j
elif board[i][j] == 'B':
bx, by = i, j
q.append((rx, ry, bx, by, 1))
visit[rx][ry][bx][by] = True
def move(x, y, dx, dy):
cnt = 0
while board[x+dx][y+dy] != '#' and board[x][y] != 'O':
x += dx
y += dy
cnt += 1
return x, y, cnt
def solve():
init()
while q:
rx, ry, bx, by, depth = q.popleft()
if depth > 10:
break
for i in range(4):
nrx, nry, rcnt = move(rx, ry, dx[i], dy[i])
nbx, nby, bcnt = move(bx, by, dx[i], dy[i])
if board[nbx][nby] != 'O':
if board[nrx][nry] == 'O':
print(depth)
return
if nrx == nbx and nry == nby:
if rcnt > bcnt:
nrx -= dx[i]
nry -= dy[i]
else:
nbx -= dx[i]
nby -= dy[i]
if not visit[nrx][nry][nbx][nby]:
visit[nrx][nry][nbx][nby] = True
q.append((nrx, nry, nbx, nby, depth+1))
print(-1)
solve()