[백준 13460] - 구슬 탈출 2]

문제

[문제 설명]

• 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 꺼내는 게임이다.
• 세로 N 가로 M의 크기의 보드이고, 빨간 구슬을 구멍을 통해서 빼냄과 동시에 파란 구슬을 구멍에 들어가지 않게 하는게 목적이다.
• 공은 중력을 사용해서 굴려야 한다.
• 빨간 공과 파란 공은 동시에 움직인다.
• 두 공은 같은 칸에 동시에 있을 수 없다.
• 더 이상 두 공 모두 움직일 수 없을 때에 이동을 멈추고 -1을 출력한다.

[실패 조건]
1. 파란 구슬이 구멍에 빠지는 경우
2. 빨간 구슬과 파란 구슬이 구멍에 동시에 빠지는 경우

[입력]
벽: #
구멍: O

[출력]
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는가?
단, 이동 횟수가 10번이 넘으면 멈추어야 한다.

해결 방법

• 접근을 하기 위해서 기본적으로 최단 시간과 동시에 움직임이라는 것에 주목을 해야 한다.
• 현재 공의 위치가 벽이나 구멍이 아닌 경우에는 앞으로 계속 나아가고, 방향에 따른 빨간 공과 파란 공의 이동 순서를 고려할 필요는 없다. 대신에 만약에 전부 특정 방향으로 이동을 하였을 때 빨간 공과 파란공의 위치가 같다면 더 많이 이동을 한 공이 뒤따라오는 공이었으니 해당 공을 현재 이동 방향의 반대로 한번 물려준다.
• 또, 전형적인 4방향 탐색을 하는 것이기 때문에 BFS 알고리즘을 사용해야 한다.

BFS 알고리즘

• 흔히 그래프 탐색이라고 하면 BFS, DFS 알고리즘이 기본적으로 존재하는데, 각각의 사용을 간단히 설명하자면 BFS는 Breadth First Search로, 최단 거리 탐색 문제에 주로 사용이 된다. 본 문제도 결국에는 최단 시간에 빨간 공이 구멍에 빠지는 경우를 찾는 것이므로 BFS로 해결 할 수 있었던 것이다.
• 한편, DFS의 경우에는 모든 노드에 방문하고자 하는 경우에 선택하게 되는 방법이다.
  - 예를 들어서 미로를 탐색 할 때에 한 방향으로 갈 수 있을 때까지 계속 이동을 하다가 더 이상 갈 수 없으면 다시 가장 가까운 갈림길로 돌아와 그 위치부터 다시 다른 방향으로 탐색을 진행하는 것이다.

주의

• 특히 나는 이런 방향을 갖고 격자 위에서 이동할 때 x, y를 헷갈리는 편이다. 그래서 이런 문제에 대비해서 일종의 규칙을 확립해 보자면
  - 가로가 M, 세로가 N일때 x는 가로 인덱스를, y는 세로 인덱스를 나타낸다. 이때 arr[y][x]이라고 격자에 접근을 해야 한다.
  • 이때 0 <= x < M, 0 <= y < N이라는 조건이 만족해야 한다.
  • 이동 방향은 위-오-아-왼 순으로 간다면
    DX = [0, 1, 0, -1], DY = [-1, 0, 1, 0]이 되어야 한다.

DX, DY = [0, 1, 0, -1], [-1, 0, 1, 0] # 위-오-아-왼
red, blue = [-1, -1], [-1, -1] # (x, y)

def check_movable(x, y):
    global board
    return board[y][x] == 'O' or board[y][x] == '#'

MIN_TIME = 1e+9

N,M = map(int, input().strip().split(' ')) # 세로, 가로
board = []
for n in range(N):
    arr = str(input())
    arr = [str(x) for x in arr]
    for m in range(M):
        if arr[m] == 'R':
            red[0] = m; red[1] = n;
            arr[m] = '.'
        elif arr[m] == 'B':
            blue[0] = m;blue[1] = n;
            arr[m] = '.' # 계속 board를 업데이트 시키는 것이 귀찮으니까 R,B 공이 있는 곳에는 빈칸으로 바꾸어 준다.

    board.append(arr)
def update_red(x, y):
    # board[y][x] = 'R'
    # board[red[0]][red[1]] = '.'
    red[0] = y
    red[1] = x

def update_blue(x, y):
    # board[y][x] = 'B'
    # board[blue[0]][blue[1]] = '.'
    blue[0] = y
    blue[1] = x

# 결국에 기울여서 중력에 의해서 움직이게 하는 것이라면 움직일 수 없을 때까지 구슬을 굴리게 될 것이다.
def move(x, y, dir, board):
    dx, dy = DX[dir], DY[dir]
    new_x, new_y = x, y
    moved = 0
    while True:
        if (0 < new_x + dx < M) and (0 < new_y + dy < N): # 범위 내에 존재하는 경우에
            if board[new_y + dy][new_x + dx] == 'O': # 빈 칸에 들어가는 경우에
                moved += 1
                return new_x + dx, new_y + dy, True, moved
            elif board[new_y + dy][new_x + dx] == '#':
                return new_x, new_y, False, moved
            elif board[new_y + dy][new_x + dx] == '.': # 빈 칸인 경우에는 당연히 움직임이 가능하다.
                moved += 1
                new_x += dx
                new_y += dy
        else:
            return new_x, new_y, False, moved
    return new_x, new_y, False, moved

def simulate(R, B, time):
    global MIN_TIME
    if time > 10:
        return -1
    for i in range(4):
        new_r_x, new_r_y, red_hole, red_moved = move(R[0], R[1], i, board)
        new_b_x, new_b_y, blue_hole, blue_moved = move(B[0], B[1], i, board)
        new_red = [new_r_x, new_r_y]
        new_blue = [new_b_x, new_b_y]
        if red_moved == 0 and blue_moved == 0: # 더이상 빨간 공과 파란 공이 움직일 수 없는 경우에는 게임을 멈춤
            continue

        if red_hole == True and blue_hole == True:
            continue

        if new_red == new_blue:
            if red_moved > blue_moved:
                new_red[0] -= DX[i]
                new_red[1] -= DY[i]
            else:
                new_blue[0] -= DX[i]
                new_blue[1] -= DY[i]

        if red_hole:
            MIN_TIME = min(MIN_TIME, time)
            return
        elif blue_hole:
            continue
        else:
            simulate(new_red, new_blue, time + 1)

simulate(red, blue, 1)

if MIN_TIME != 1e+9:
    print(MIN_TIME)
else:
    print(-1)

## 13460-구슬 탈출 2 문제에서 시간 단축을 할 수 있는 방법
from collections import deque

DX, DY = [0, 1, 0, -1], [-1, 0, 1, 0]
N, M = map(int, input().strip().split(' ')) # 세로, 가로
board = []

for n in range(N):
    arr = str(input())
    arr = [str(x) for x in arr]
    for m in range(M):
        if arr[m] == 'R':
            a, b = n, m
        elif arr[m] == 'B':
            c, d=  n, m
    board.append(arr)

visited = [[[[False for _ in range(M)] for _ in range(N)] for _ in range(M)] for _ in range(N)]

dQ = deque()
dQ.append((a, b, c, d, 1)) # red_y, red_x, blue_y, blue_x, time
visited[a][b][c][d] = True

def move(x, y, i):
    dx, dy = DX[i], DY[i]
    count = 0
    while board[x + dx][y + dy] != '#' and board[x][y] != 'O':
        x, y = x + dx, y + dy
        count += 1
    return x, y, count

def bfs():
    while dQ:
        a, b, c, d, time = dQ.popleft()
        if time > 10:
            break
        for i in range(4):
            na, nb, red_cnt = move(a, b, i)
            nc, nd, blue_cnt = move(c, d, i)
            if board[na][nb] == 'O' and board[nc][nd] != 'O': # 빨간공만 구멍에 들어가고 파란 공은 구멍에 들어가지 않은 경우
                return time
            if board[nc][nd] != 'O':
                if na == nc and nb == nd:
                    if red_cnt > blue_cnt:
                        na -= DX[i]; nb -= DY[i]
                    else:
                        nc -= DX[i]; nd  -= DY[i];
                if visited[na][nb][nc][nd] == False:
                    visited[na][nb][nc][nd] = True
                    dQ.append((na, nb, nc, nd, time+1))

    return -1
print(bfs())