개발자입니다
[백준] 13460번 구슬 탈출 2 본문
구슬 탈출 2
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
| 2 초 | 512 MB | 100372 | 30902 | 17800 | 28.411% |
문제
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.
입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
출력
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
예제 입력 1
5 5
#####
#..B#
#.#.#
#RO.#
#####
예제 출력 1
1
예제 입력 2
7 7
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######
예제 출력 2
5
예제 입력 3
7 7
#######
#..R#B#
#.#####
#.....#
#####.#
#O....#
#######
예제 출력 3
5
예제 입력 4
10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.#.#..#
#...#.O#.#
##########
예제 출력 4
-1
예제 입력 5
3 7
#######
#R.O.B#
#######
예제 출력 5
1
예제 입력 6
10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.##...#
#O..#....#
##########
예제 출력 6
7
예제 입력 7
3 10
##########
#.O....RB#
##########
예제 출력 7
-1
내 코드
미완성
from collections import deque
DIRECTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)] # 상하좌우
def get_tilt_count(N, M, board):
R = '' # 빨간 구슬 좌표
B = '' # 파란 구슬 좌표
# 구슬 위치 조사
for j in range(N):
for i in range(M):
if board[j][i] == '.':
continue
elif board[j][i] == 'R':
R = (i, j)
elif board[j][i] == 'B':
B = (i, j)
tilts = 0
queue = deque([(*R, *B, tilts)]) # R B 구슬 위치, 이동 횟수 저장
visited = set() # 빨간 구슬, 파란 구슬 위치 저장
visited.add((R, B))
while queue:
Rx, Ry, Bx, By, tilts = queue.popleft()
for dx, dy in DIRECTIONS: # bfs: 상하좌우로 기울이기
R_flag = True
# R과 B 중 먼저 이동할 것 찾기
if (dy == -1 and By < Ry) or (dy == 1 and By > Ry) or (dx == -1 and Bx < By) or (dx == 1 and Bx > By):
# 상 or 하 or 좌 or 우 이동시 B가 R 앞에 있으면 먼저 이동
R_flag = False
# R 먼저 이동이면
if R_flag:
# 벽 제외까지 한 칸 씩 전진
for step in range(1, 10 - 2):
# 다음 위치 구함
nRx, nRy = Rx + dx * step, Ry + dy * step
# .이면 계속 검사
if (nRx, nRy) == '.':
continue
# #이면 검사 중지하고 그 전 위치로 이동 후 queue에 넣기
if board[nRy][nRx] == '#':
board[Ry][Rx], board[nRy][nRx] = '.', 'R' # 기존 위치 변경
## B 이동
if (nBx, nBy) == '.':
continue
# #이면 검사 중지하고 그 전 위치로 이동 후 queue에 넣기
if board[nBy][nBx] in ('#', 'R') :
board[By][Bx], board[nBy][nBx] = '.', 'B' # 기존 위치 변경
visited = (nRx - dx, nRy - dy, nBx - dx, ) # 방문처리 아이템
queue_item = (nRx - dx, nRy - dy) # 이동위치 저장 아이템
nBx, nBy = Bx + dx * step, By + dy * step
# B 먼저 이동이면
else:
N, M = map(int, input().split()) # 세로, 가로
board = [list(input()) for _ in range(N)]
print(get_tilt_count(N, M, board))
다시 풀었을때 GPT 보다 코드가 더 길다.
크기 벗어나는지 검사도 불필요 한 것 같다.
from collections import deque
DIRECTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)] # 상하좌우
def moves(x, y, dx, dy, board):
nx, ny = x, y
step = 0
for step in range(1, 8): # 최대 길이 10이므로 7까지 검사
nx, ny = x + dx * step, y + dy * step
# 크기 벗어나는지
if 0 <= nx < M and 0 <= ny < N:
# 구멍에 빠졌나
if board[ny][nx] == 'O':
break
# #인지 검사
elif board[ny][nx] == '#':
nx = x + dx * (step - 1)
ny = y + dy * (step - 1)
step -= 1
break
return nx, ny, step
def bfs(board, rx, ry, bx, by):
count = 0
queue = deque([(rx, ry, bx, by, count)]) # R B 구슬 위치, 이동 횟수 저장
visited = set() # 빨간 구슬, 파란 구슬 위치 저장
visited.add((rx, ry, bx, by))
while queue:
rx, ry, bx, by, count = queue.popleft()
if count > 10: # 기울인 횟수가 10회 초과하면 -1 리턴
return -1
if board[by][bx] == 'O': # 파란구슬 빠지면 다음 큐
continue
if board[ry][rx] == 'O' and board[by][bx] != 'O': # 빨간구슬 빠지고 파란구슬 안빠지면 count 리턴
return count
for dx, dy in DIRECTIONS: # bfs: 상하좌우로 기울이기
nrx, nry, step_r = moves(rx, ry, dx, dy, board)
nbx, nby, step_b = moves(bx, by, dx, dy, board)
# 더 먼거리 이동한 구슬 한 칸 뒤로(같은 길 이동시)
if (nrx, nry) == (nbx, nby) and board[nby][nbx] != 'O':
if step_r > step_b:
nrx, nry = nrx - dx, nry - dy
elif step_r < step_b:
nbx, nby = nbx - dx, nby - dy
# 방문 안했으면 추가
if (nrx, nry, nbx, nby) not in visited:
queue.append((nrx, nry, nbx, nby, count + 1))
visited.add((nrx, nry, nbx, nby))
return -1 # queue가 비면 -1 리턴
# 구슬 위치 조사
def get_tilt_count(N, M, board):
rx = ry = bx = by = -1
for j in range(N):
for i in range(M):
if board[j][i] == 'R':
rx, ry = (i, j)
elif board[j][i] == 'B':
bx, by = (i, j)
return bfs(board, rx, ry, bx, by)
N, M = map(int, input().split()) # 세로, 가로
board = [list(input()) for _ in range(N)]
print(get_tilt_count(N, M, board))
chatGPT
이 문제는 너비 우선 탐색(BFS) 을 이용하여 최소 횟수를 찾는 전형적인 그래프 탐색 문제입니다.
풀이 접근
- 보드에서 'R', 'B', 'O'의 위치를 찾는다.
- BFS를 이용하여 최소 횟수를 찾는다.
- 네 방향(상, 하, 좌, 우)으로 기울일 때, 빨간 구슬과 파란 구슬을 적절하게 움직인다.
- 파란 구슬이 구멍('O')에 빠지면 실패.
- 빨간 구슬이 구멍('O')에 빠지고, 파란 구슬이 빠지지 않으면 성공.
- 각 상태(빨간 구슬 위치, 파란 구슬 위치)를 방문 체크하여 중복 방지를 한다.
- 기울일 때 두 구슬이 겹치는 경우를 고려해야 한다.
- 같은 위치로 이동하면, 원래 위치를 기준으로 더 늦게 도착한 구슬을 한 칸 뒤로 이동시킨다.
- 최대 10번 움직였을 때도 해결이 안 되면 -1을 반환한다.
코드 개선 후 정답 코드
아래는 BFS를 이용한 최적화된 풀이입니다.
from collections import deque
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상, 하, 좌, 우
def move(x, y, dx, dy, board):
count = 0
while board[y + dy][x + dx] != "#" and board[y][x] != "O":
x += dx
y += dy
count += 1
return x, y, count
def bfs(N, M, board, rx, ry, bx, by):
queue = deque([(rx, ry, bx, by, 0)])
visited = set()
visited.add((rx, ry, bx, by))
while queue:
rx, ry, bx, by, depth = queue.popleft()
if depth >= 10:
return -1
for dx, dy in DIRECTIONS:
nrx, nry, rcnt = move(rx, ry, dx, dy, board)
nbx, nby, bcnt = move(bx, by, dx, dy, board)
if board[nby][nbx] == "O": # 파란 구슬이 빠지면 실패
continue
if board[nry][nrx] == "O": # 빨간 구슬만 빠지면 성공
return depth + 1
# 두 구슬이 같은 위치면 이동한 거리가 많은 쪽을 뒤로 보냄
if nrx == nbx and nry == nby:
if rcnt > bcnt:
nrx -= dx
nry -= dy
else:
nbx -= dx
nby -= dy
if (nrx, nry, nbx, nby) not in visited:
visited.add((nrx, nry, nbx, nby))
queue.append((nrx, nry, nbx, nby, depth + 1))
return -1
def get_tilt_count(N, M, board):
rx = ry = bx = by = 0
for y in range(N):
for x in range(M):
if board[y][x] == "R":
rx, ry = x, y
elif board[y][x] == "B":
bx, by = x, y
return bfs(N, M, board, rx, ry, bx, by)
N, M = map(int, input().split())
board = [list(input().strip()) for _ in range(N)]
print(get_tilt_count(N, M, board))코드 설명
- move 함수
- 한 방향으로 기울일 때, 벽이나 구멍을 만날 때까지 이동한다.
- 이동한 거리(count)도 함께 반환하여 나중에 구슬이 겹칠 경우 처리할 때 사용한다.
- bfs 함수
- queue를 사용하여 BFS 탐색을 수행한다.
- 빨간 구슬과 파란 구슬을 각각 이동시킨 후:
- 파란 구슬이 빠지면 무시.
- 빨간 구슬이 빠지면 정답 반환.
- 두 구슬이 겹치는 경우 더 멀리 이동한 구슬을 한 칸 뒤로 보낸다.
- 방문한 상태를 visited에 기록하여 중복 탐색을 방지한다.
- 10번 이상 움직이면 1 반환.
- get_tilt_count 함수
- 보드에서 빨간 구슬(R)과 파란 구슬(B)의 위치를 찾고 bfs를 호출한다.
시간 복잡도 분석
- BFS 탐색이며, 가능한 상태가 많아보이지만 실제로 10번 이내의 이동만 고려하면 된다.
- 최악의 경우에도 O(4^10) ≈ 10^6로 충분히 해결 가능하다.
개선점
- 기존 코드의 문제점
- 이동 시 벽을 제대로 체크하지 못함.
- BFS에서 방문 상태를 올바르게 관리하지 않음.
- queue에 올바른 상태를 추가하는 로직이 부족함.
- 개선 후 코드
- move 함수를 통해 이동을 간결하게 처리.
- bfs에서 방문 체크와 조건을 제대로 처리하여 성능과 가독성 개선.
이제 더 최적화된 풀이로 문제를 해결할 수 있습니다! 🚀
부가 질문
내 생각
- visited, queue를 설계하는 건 맞게 했다.
- 어떤 구슬을 먼저 이동할지 설계를 잘못했다. 이동할 구슬을 찾을 생각을 했는데 이동 후에 더 먼 거리를 이동한 구슬을 한 칸 뒤로 이동한다는 생각을 못했다. 한 번 이동시 구슬의 이동 칸을 비교해서 더 먼 구슬을 한 칸 뒤로 옮겨야 한다.
- 함수를 여러개로 나눠서 중복코드를 줄이는 것을 고려하지 않았다. 구슬 위치 찾는 함수, bfs 함수, 구슬 이동 함수를 별도로 해야한다.
'코딩테스트 > Python 문제풀기' 카테고리의 다른 글
| [백준] 16930번 달리기 (0) | 2025.02.05 |
|---|---|
| [백준] 17086번 아기 상어 2 (0) | 2025.02.04 |
| [백준] 14226번 이모티콘 (0) | 2025.02.02 |
| [백준] 13913번 숨바꼭질 4 (0) | 2025.01.31 |
| [백준] 13549번 숨바꼭질3 (0) | 2024.11.23 |