[BOJ] 13460번. 구슬탈출2

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

풀이

• BFS를 사용하는 문제
• 4가지(위쪽, 오른쪽, 아래쪽, 왼쪽)에 대해 빨간공, 파란공이 움직인 결과, 이동 거리 정보가 필요
  • 움직일때 격자 밖으로 벗어나지 않고, '#'이 아니고, 현재 위치가 'O'이 아니면 해당 방향으로 한칸씩 계속 이동
• 이동했는데, 빨간공, 파란공이 겹칠 때 이동거리를 기준으로 위치를 다시 조정해줌

# 입력 받기
n, m = map(int, input().split())
board = [list(map(str, input())) for _ in range(n)]

# 위쪽, 오른쪽, 아래쪽, 왼쪽 순
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 빨간공, 파란공 위치 알아내기
rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
    for j in range(m):
        if board[i][j] == 'R':
            rx, ry = i, j
        if board[i][j] == 'B':
            bx, by = i, j

# 중복 방문 방지를 위해 visited 배열 생성
visited = [[[[0 for _ in range(m)] for _ in range(n)] for _ in range(m)] for _ in range(n)]

# BFS를 사용해 문제를 풀것임. (빨간공 좌표, 파란공 좌표, count)를 넣고, count가 10보다 클 경우 -1 return하기.
queue = [(rx, ry, bx, by, 1)]
visited[rx][ry][bx][by] = 1

def move(x, y, mx, my):
    # c는 이동거리
    c = 0
    while 0 <= x+mx <= (n-1) and 0 <= y+my <= (m-1) and board[x + mx][y + my] != '#' and board[x][y] != 'O':
        x, y = x+mx, y+my
        c += 1
    return x, y, c

def BFS():
    while queue:
        #print(queue)
        q = queue.pop(0)
        rx, ry, bx, by, count = q[0], q[1], q[2], q[3], q[4]
        # 최대 움직임 수는 10가지
        if count > 10:
            print(-1)
            return
        else:
            for i in range(4):
                n_rx, n_ry, n_r_count = move(rx, ry, dx[i], dy[i])
                n_bx, n_by, n_b_count = move(bx, by, dx[i], dy[i])

                # 파란 공이 구멍에 도달함 -> continue를 사용 해당 방향으로 움직인 경우에 대해 더 이상 탐색해하지 않음.
                if board[n_bx][n_by] == 'O':
                    continue

                # 빨간 공이 구멍에 도달함 -> 현재 count를 출력 후 함수 종료.
                if board[n_rx][n_ry] == 'O':
                    print(count)
                    return

                # 빨간 공과 파란 공이 같은 좌표에 도달했을 경우 -> 더 많이 이동한 공을 해당 방향 반대 방향으로 한칸 움직임.
                if n_rx == n_bx and n_ry == n_by:
                    if n_r_count > n_b_count:
                        n_rx, n_ry = n_rx-dx[i], n_ry-dy[i]
                    else:
                        n_bx, n_by = n_bx-dx[i], n_by-dy[i]

                if visited[n_rx][n_ry][n_bx][n_by] == 0:
                    visited[n_rx][n_ry][n_bx][n_by] = 1
                    queue.append((n_rx, n_ry, n_bx, n_by, count + 1))
    print(-1)

BFS()