[BOJ/Python] 13460.구슬 탈출 2

📌 문제

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

📌 문제 접근 방법

1. 입력 값을 모두 받아준 뒤, 빨간 공과 파란 공의 좌표를 찾아줬다.
2. answer는 10을 넘어가면 -1을 리턴하므로 11로 초기화해준뒤, answer가 갱신되지 않고 그대로 11로 남아있으면 -1을 출력하도록 해줬다.
3. move 함수는 (공의 행좌표, 열좌표, 행방향, 열방향)을 매개변수로 가진다.
   1. 한 번의 이동이 아닌, 벽을 만날 때까지 쭉 이동해야하므로 while문을 사용한다.
   2. dx, dy를 더해주면서 공을 이동시킨다.
   3. 만약 공이 구멍을 만나서 탈출했다면 공이 있던 위치를 '.'으로 바꾸고 (0, 0)을 리턴한다.
   4. 공이 벽을 만나서 더이상 이동이 불가하다면, 공의 새로운 위치에 'R' 또는 'B'를 표시하고, 원래 공의 위치는 '.'으로 바꾼 뒤 공의 새로운 위치를 리턴한다.
4. restore 함수는 (빨간 공의 원래 위치, 새로운 위치, 파란 공의 원래 위치, 새로운 위치)를 매개변수로 가진다.
   1. 빨간 공의 원래 위치에 다시 'R'표시를 해준다.
   2. 빨간 공이 탈출하지 않았고 (새로운 위치가 (0, 0)이 아니고), 원래 위치에서 이동을 했다면 (원래 위치와 새로운 위치가 다르다면), 빨간 공의 새로운 위치를 '.'으로 바꿔준다.
   3. 파란 공도 마찬가지로 진행을 하는데, 새로운 위치를 '.'으로 바꿔줄 때, 그 위치가 'R'이 아닌지 체크하는 조건을 추가해주어야 한다. (이걸 안해서 40%대에서 틀렸습니다가 떴다..ㅜㅜ..)
      4-1의 과정에서 빨간 공을 원래 위치로 되돌렸는데, 이게 파란 공의 새로운 위치와 같을 경우 4-3에서 다시 '.'으로 바꿔버리기 때문에 해당 조건이 꼭!! 필요하다.
5. game 함수는 (보드를 기울인 횟수, 빨간 공 좌표, 파란 공 좌표)를 매개변수로 가진다.
   1. 만약 cnt가 answer보다 크거나 같다면 더 이상 확인해줄 필요가 없기 때문에 바로 리턴해준다.
   2. 반복문을 활용해서 아래, 왼쪽, 위, 오른쪽의 순서로 네 방향을 확인해준다.
   3. 빨간 공과 파란 공의 다음 위치가 '.' 또는 'O'가 아니라면 이동이 불가하므로 해당 방향은 continue를 사용해서 넘겨버린다.
   4. 현재 방향으로 이동이 가능하다면 빨간 공과 파란 공 중 어떤 공을 먼저 이동시킬지 결정한다.
      (아래쪽으로 이동하는 경우, 두 개의 공 중에서 더 아래쪽에 있는 공부터 이동시킨다. 그래야 두 개의 공이 같은 열에 있을 때 중간에 멈추지 않고 제일 아래쪽까지 이동할 수 있기 때문이다.)
   5. 먼저 움직일 공을 결정했다면 순서에 따라 move함수를 통해 공을 이동시킨다.
   6. 5의 이동 후, 만약 빨간 공이 구멍으로 빠져나가고 파란 공은 빠져나가지 않았다면 구슬 탈출에 성공한 것이므로 answer를 갱신시킨다.
   7. 5의 이동 후, 두 공이 모두 구멍으로 빠져나가지 못했다면 다른 움직임이 필요하므로 cnt를 1 증가시켜서 다시 game 함수를 실행시킨다.
   8. 5의 이동 후, 파란 공이 구멍으로 빠져나가게 되었다면 해당 움직임은 실패이므로 다시 되돌려야한다.
   9. 7의 경우에는 해당 이동을 하지 않은 경우도 살펴봐야 하므로 움직임을 다시 되돌려야한다.
   10. 따라서 restore함수를 사용해서 현재 진행했던 이동을 다시 되돌려준다.
6. 모든 시행이 끝난 뒤 answer 값에 따라 정답을 출력한다.

 

📌 코드

# 백준 13460 구슬 탈출2

def move(x, y, dx, dy):
    global board

    origin = (x, y)

    while True:
        x += dx
        y += dy
        if board[x][y] == 'O':
            board[origin[0]][origin[1]] = '.'
            return (0, 0)
        elif board[x][y] != '.':
            if (x-dx, y-dy) != origin:
                board[x-dx][y-dy] = board[origin[0]][origin[1]]
                board[origin[0]][origin[1]] = '.'
            return (x-dx, y-dy)


def restore(red, mr, blue, mb):
    global board

    board[red[0]][red[1]] = 'R'
    if mr != (0, 0) and red != mr:
        board[mr[0]][mr[1]] = '.'
    board[blue[0]][blue[1]] = 'B'
    if mb != (0, 0) and blue != mb and board[mb[0]][mb[1]] != 'R':
        board[mb[0]][mb[1]] = '.'


def game(cnt, red, blue):
    global board, answer

    if cnt >= answer:
        return
    
    for i in range(4):
        # 둘 다 이동할 수 없는 상태
        if board[red[0]+dxy[i][0]][red[1]+dxy[i][1]] not in ('.', 'O') and board[blue[0]+dxy[i][0]][blue[1]+dxy[i][1]] not in ('.', 'O'):
            continue

        # 해당 방향쪽에 있는 공부터 움직이도록
        if (i == 0 and red[0] < blue[0]) or (i == 1 and blue[1] < red[1]) or (i == 2 and blue[0] < red[0]) or (i == 3 and red[1] < blue[1]):
            mb = move(blue[0], blue[1], dxy[i][0], dxy[i][1])
            mr = move(red[0], red[1], dxy[i][0], dxy[i][1])
        else:
            mr = move(red[0], red[1], dxy[i][0], dxy[i][1])
            mb = move(blue[0], blue[1], dxy[i][0], dxy[i][1])

        # 빨간 공은 구멍으로 빠져나가고 파란 공은 빠져나가지 않은 경우
        if mr == (0, 0) and mb != (0, 0):
            answer = min(answer, cnt)
        # 두 공 모두 구멍으로 빠져나가지 못한 경우
        elif mb != (0, 0):
            game(cnt+1, mr, mb)
            
        restore(red, mr, blue, mb)


N, M = map(int, input().split())

board = []
for _ in range(N):
    board.append(list(input()))

for i in range(N):
    for j in range(M):
        if board[i][j] == 'R':
            red = (i, j)
        elif board[i][j] == 'B':
            blue = (i, j)

dxy = [(1, 0), (0, -1), (-1, 0), (0, 1)] # 아 왼 위 오

answer = 11
game(1, red, blue)

if answer == 11:
    print(-1)
else:
    print(answer)