구슬 탈출
문제 파악Permalink
주어진 보드에서 빨간 구슬과 파란 구슬을 굴려서 빨간 구슬만 구멍에 넣을 수 있는지 확인하는 문제이다. 구슬은 상하좌우로 기울여서 굴릴 수 있으며, 빨간 구슬은 구멍에 빠지면 성공이고, 파란 구슬이 빠지면 실패로 간주한다. 최대 10번의 시도안에 빨간 구슬만 구멍에 들어가는지 확인해야 한다.
접근 방법Permalink
- 빨간 구슬과 파란 구슬의 초기 위치를 파악한다.
- 네 방향으로 구슬을 굴려가면서 구슬의 이동을 시뮬레이션 한다.
- 구슬이 이동하는 동안 벽에 부딪히거나 다른 구슬과 겹치는 등의 상황을 처리
- 빨간 구슬만 구멍에 빠지면 성공, 최대 10번안에 성공여부 반환
코드 구현Permalink
from collections import deque
N, M = map(int, input().split())
board = [list(input().rstrip()) for _ in range(N)]
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(N, M):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
visited = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]
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
queue.append((rx, ry, bx, by, 1))
visited[rx][ry][bx][by] = True
while queue:
rx, ry, bx, by, depth = queue.popleft()
if depth > 10:
return False
for i in range(4):
nrx, nry, r_cnt = move(rx, ry, dx[i], dy[i])
nbx, nby, b_cnt = move(bx, by, dx[i], dy[i])
if board[nbx][nby] != 'O':
if board[nrx][nry] == 'O':
return True
if nrx == nbx and nry == nby:
if r_cnt > b_cnt:
nrx -= dx[i]
nry -= dy[i]
else:
nbx -= dx[i]
nby -= dy[i]
if not visited[nrx][nry][nbx][nby]:
visited[nrx][nry][nbx][nby] = True
queue.append((nrx, nry, nbx, nby, depth + 1))
return False
if solve(N, M):
print(1)
else:
print(0)
Leave a comment