[ 문제 설명 ]
https://www.acmicpc.net/problem/13460
요약: N x M 보드에서 빨간 구슬을 구멍에 빼내는 최소 이동 횟수를 구하는 문제 (파란 구슬은 빠지면 안 됨).
제약 조건: 10번 이하로 움직여서 빼내지 못하면 -1 출력.
[ 접근 방식 ]
구슬이 좌표에 주어지고 구멍을 찾아가는 동작을 시작점에서부터 동시다발적으로 퍼져나가는 상황이라고 판단하여 BFS를 통해 목적지에 가장 먼저 도착하는 경우의 수를 도출하고자 하였다.
주요 로직
- 빨간 구슬과 파란 구슬이 동시에 움직이므로, 방문 체크는 (rx, ry, bx, by) 4차원 데이터를 기준으로 해야 한다.
- 이를 visited = set()에 (rx, ry, bx, by) 튜플 형태로 저장하여 처리하도록 구현했다.
- move() 함수: 한 칸씩 이동하는 것이 아니라, 벽(#)이나 구멍(O)을 만날 때까지 계속 이동해야 하므로 while 문을 사용하여 구현했다.
- 충돌 처리: 두 구슬이 이동 후 같은 좌표에 멈췄을 때, '이동 거리가 더 긴 구슬'이 더 뒤에서 출발했다는 뜻이므로 한 칸 뒤로 물러나게 처리했다.
[ 전체 코드 ]
import sys
from collections import deque
# 시간 초과를 방지하기 위해 사용 -> 맨 뒤에 \n을 포함해서 가져오게 되므로 이를 아래와 같이 해결해야 함
# 숫자 입력 받을 때: .split() 사용 / 문자열 입력 받을 때: .strip() 사용 -> 맨 뒤의 \n 제거하기 위함
input = sys.stdin.readline
def solve():
N, M = map(int, input().split()) # N, M을 정수로 각각 입력 받도록 map 함수를 사용해서 저장
# board에 입력되는 문자열을 list 형태로 저장해줌
# 현재 반복이 몇번째인지 알 필요 없으므로 for _ in range(N)으로 N번 반복만 하는 것을 강조
board = [list(input().strip()) for _ in range(N)]
# 빨간 구슬과 파란 구슬의 (x, y) 좌표를 저장할 변수 초기화
rx, ry, bx, by = 0, 0, 0, 0
# R과 B가 board 좌표 중 어디에 위치해있는지 초기 설정을 찾기 위해 반복
# 가로, 세로를 정해서 설정한 후 변수에 각 좌표값을 저장
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
# (rx, ry, bx, by, 1)이라는 튜플이 q라는 queue에 저장되게 된다.
# 빨간 구슬 위치와 파란 구슬 위치, depth로 표현되는 이동 횟수가 한 번에 튜플로 저장된다.
q = deque([(rx, ry, bx, by, 1)])
# 빨간 구슬과 파란 구슬이 방문한 좌표를 저장해서 다시 방문하는 일을 방지
visited = set([(rx, ry, bx, by)])
# 헷갈리지 않게 조심해야함 / x좌표가 줄어들고 늘어나면 row값이 변동하므로 상,하 이동
# x 좌표(상,하)로 이동할때 사용
dx = [-1, 1, 0, 0]
# y 좌표(좌,우)로 이동할 때 사용
dy = [0, 0, -1, 1]
# 구슬이 움직이는 동작을 구현하기 위해 함수 정의
def move(x, y, dx, dy):
count = 0 # 이동 횟수를 저장할 변수 초기화
# board에서 구슬들이 이동할 다음칸이 '#', 현재 칸이 'O'를 만나지 않는다면 계속해서 실행
while board[x + dx][y + dy] != '#' and board[x][y] != 'O':
x += dx # x 좌표에 dx만큼 움직이도록 함
y += dy # y 좌표에 dy만큼 움직이도록 함
count += 1 # 움직였다면 count 1 증가
return x, y, count # (x, y) 좌표와 count 반환
# 큐의 요소만큼 반복 실행
while q:
# 큐에서 pop을 통해 가장 먼저 입력된 튜플부터 실행한다.
# pop한 후 각 변수에 튜플에 해당하는 값을 저장
rx, ry, bx, by, depth = q.popleft()
# 만약 이동 횟수가 10을 초과하면 중단
if depth > 10:
break
# 상,하,좌,우 4가지 방향으로 board를 기울여서 구슬들을 이동시킬 수 있으므로 4번 반복하도록 설정
# i값이 0부터 3까지 변하므로 i가 변할 때마다 네 방향중 한 방향으로 기울여진다.
for i in range(4):
# move 함수가 실행되고 return 값이 각 변수에 인덱스에 맞게 저장된다.
nrx, nry, r_cnt = move(rx, ry, dx[i], dy[i])
nbx, nby, b_cnt = move(bx, by, dx[i], dy[i])
# 구슬이 구멍에 빠지는 상황을 고려할 때,
# 파란 구슬을 먼저 확인해야한다.
# -> 동시에 파란 구슬과 빨간 구슬이 빠지게 되면 실패로 간주되므로 빨간 구슬을 먼저 확인하면 성공으로 판단될 수 있기 때문
# 만약 파란 구슬의 좌표에 'O'이라면 계속해서 진행한다.
if board[nbx][nby] == 'O':
continue
# 만약 빨간 구슬의 좌표에 'O'이라면 그 때의 이동 횟수를 출력하고 반환한다.
if board[nrx][nry] == 'O':
print(depth)
return
# 만약 빨간 구슬과 파란 구슬의 좌표가 겹친다면
if nrx == nbx and nry == nby:
# 둘 중 어떤 구슬이 더 많이 이동했는지를 확인하고,
# 많이 이동한 구슬이 그렇지 않은 구슬 한 칸 뒤로 이동하게 된다.
if r_cnt > b_cnt:
nrx -= dx[i]
nry -= dy[i]
else:
nbx -= dx[i]
nby -= dy[i]
# 만약 visited에 빨간 구슬과 파란 구슬의 좌표가 속해있지 않다면
if (nrx, nry, nbx, nby) not in visited:
# 해당 튜플을 visited에 추가해준다.
visited.add((nrx, nry, nbx, nby))
# 그리고 큐에 추가하고 이동 횟수를 1 증가시킨다.
q.append((nrx, nry, nbx, nby, depth + 1))
#
print(-1)
if __name__ == "__main__":
solve()
[ 마무리 ]
빨간 구슬과 파란 구슬의 이동 좌표를 동시에 기록할 필요가 있어서 visited 변수에 이를 저장하고자 하였다. 처음에는 N x M x N x M 크기의 4차원 배열을 선언하는 방식을 고려했다. 하지만 이는 방문하지 않을 좌표까지 미리 공간을 할당해야 하므로 메모리 낭비가 심하다고 판단했다. 이때 set에 튜플을 저장하는 방식을 통해 실제로 탐색한 좌표만 저장하도록 구현해 효율적으로 저장할 수 있었다.