728x90
문제 설명
구슬 탈출은 빨간 구슬을 구멍에 넣는 것이 목표인 게임이다. 직사각형 보드에 빨간 구슬과 파란 구슬이 각각 하나씩 놓여 있으며, 보드를 기울여 구슬들을 움직일 수 있다. 중요한 점은 파란 구슬은 구멍에 들어가면 안 되고, 빨간 구슬만 구멍에 빠져야 한다.
보드를 왼쪽, 오른쪽, 위, 아래로 기울일 수 있으며, 한 번 기울일 때마다 구슬들은 그 방향으로 모두 이동할 수 있을 만큼 이동한다. 두 구슬은 동시에 움직이며, 이동 중에 서로 겹칠 수 없다.
목표는 최소 횟수로 빨간 구슬을 구멍에 넣는 것이다. 단, 이동 횟수는 10번을 초과할 수 없다. 그렇다면 어떻게 이 문제를 해결할 수 있을까?
해결 방법: BFS를 활용한 상태 탐색
이 문제는 구슬들의 모든 가능한 상태를 탐색하여 최소 횟수로 빨간 구슬을 구멍에 넣는 경로를 찾는 것이다. 여기서 BFS(너비 우선 탐색) 알고리즘을 사용하면 최단 경로를 효율적으로 찾을 수 있다.
BFS란?
BFS는 그래프 탐색 알고리즘 중 하나로, 시작 노드에서부터 인접한 노드를 모두 방문한 후, 그 다음 레벨의 노드들을 방문하는 방식이다. 이 방법을 사용하면 최단 경로를 보장할 수 있어 이 문제에 적합하다.
구체적인 해결 단계
- 입력 처리 및 초기 상태 설정
- 보드를 입력받고, 빨간 구슬(R), 파란 구슬(B), 구멍(O)의 위치를 파악한다.
- 구슬들의 위치를 저장하고, 보드에서 구슬을 제거하여 이동 시 간섭을 피한다.
- 구슬 이동 함수 구현
- 네 가지 방향(상, 하, 좌, 우)에 대해 구슬을 이동시키는 함수를 작성한다.
- 구슬은 벽(#)이나 구멍(O)을 만나기 전까지 이동한다.
- 이동 중 구멍에 빠지면 해당 정보를 반환한다.
- 두 구슬이 같은 위치에 도달하면 이동 거리를 비교하여 뒤에 온 구슬을 한 칸 뒤로 이동시킨다.
- BFS를 통한 상태 탐색
- 큐(queue)를 사용하여 BFS를 구현한다.
- 초기 상태(빨간 구슬 위치, 파란 구슬 위치, 이동 횟수)를 큐에 넣는다.
- 방문한 상태를 기록하기 위해 4차원 배열을 사용한다: visited[빨간X][빨간Y][파란X][파란Y]
- 큐에서 상태를 하나씩 꺼내 네 방향으로 구슬을 이동시키고 새로운 상태를 생성한다.
- 이동 횟수가 10을 초과하면 실패로 간주한다.
- 파란 구슬이 구멍에 빠지면 해당 상태는 무시한다.
- 빨간 구슬이 구멍에 빠지면 현재 이동 횟수를 반환한다.
- 결과 출력
- BFS 탐색 중 빨간 구슬을 구멍에 넣는 경우를 찾으면 그때의 이동 횟수를 출력한다.
- 10번 이내에 해결하지 못하면 -1을 출력한다.
from collections import deque
# 이동 방향 설정: 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def move(x, y, dx, dy, board):
count = 0
# 다음 위치가 벽이 아니고 구멍이 아닐 때까지 이동한다.
while board[x + dx][y + dy] != '#' and board[x][y] != 'O':
x += dx
y += dy
count += 1
if board[x][y] == 'O':
break
return x, y, count
def bfs(board, rx, ry, bx, by):
n, m = len(board), len(board[0])
visited = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
queue = deque()
queue.append((rx, ry, bx, by, 0))
visited[rx][ry][bx][by] = True
while queue:
rx, ry, bx, by, depth = queue.popleft()
if depth >= 10:
return -1
for i in range(4):
nrx, nry, rc = move(rx, ry, dx[i], dy[i], board)
nbx, nby, bc = move(bx, by, dx[i], dy[i], board)
# 파란 구슬이 구멍에 빠진 경우
if board[nbx][nby] == 'O':
continue
# 빨간 구슬이 구멍에 빠진 경우 성공
if board[nrx][nry] == 'O':
return depth + 1
# 두 구슬이 같은 위치에 있는 경우 처리
if nrx == nbx and nry == nby:
if rc > bc:
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 -1
def main():
N, M = map(int, input().split())
board = [list(input()) for _ in range(N)]
rx = ry = bx = by = 0
for i in range(N):
for j in range(M):
if board[i][j] == 'R':
rx, ry = i, j
board[i][j] = '.'
elif board[i][j] == 'B':
bx, by = i, j
board[i][j] = '.'
result = bfs(board, rx, ry, bx, by)
print(result)
if __name__ == '__main__':
main()
728x90
'Python > 백준' 카테고리의 다른 글
백준 테트로미노 [14500] Python 코드 + 해설 (0) | 2024.10.22 |
---|---|
백준 주사위 굴리기 [14499] Python 코드 + 해설 (0) | 2024.10.22 |
백준 시험 감독 [13458] Python 코드 + 해설 (1) | 2024.10.22 |
백준 뱀 [3190] Python 코드 + 해설 (0) | 2024.10.22 |
백준 2048 (Easy) [12100] Python 코드 + 해설 (0) | 2024.10.22 |