[백준 13460] 구슬 탈출 2

문제 보기

이 문제는 BFS에 브루트포스를 응용한 문제이다.

처음에 문제를 읽을 당시에는 어떻게 코드를 짜야할 지 몰랐지만, 질문게시판을 뒤지다 보니 영감을 얻었다.

한 번 방문할 때마다 각 방향을 탐색하는 건 기존의 BFS 동일하다.

하지만 판을 기울일 때 벽, 구멍 또는 다른 공에 닿을 때까지 직진을 해야한다는 것에 주의해야 한다.

또 주의해야할 점은, 두 개의 공을 굴려서 같은 곳에서 멈추는 경우에는, 공이 굴러간 거리를 계산한 뒤, 굴러간 거리가 더 긴 공을 다시 굴러왔던 방향으로 1번 이동해야 한다. (그렇게 해야 공이 겹치지 않는다. 60~65번째 줄 참고)

67~69번째 줄을 보면 다음과 같은데, 이 부분의 코드가 없으면 count가 11이상이 되는 반례가 생긴다.

            # prevent count from being over 10

            if count == 10:

                return -1

import sys
from queue import Queue
 
n, m = map(int, sys.stdin.readline().split())
board = [[0 for c in range(m)] for r in range(n)]
R = (0, 0)
B = (0, 0)
EXIT = (0, 0)
 
for i in range(n):
    line = sys.stdin.readline()
    for j in range(m):
        board[i][j] = line[j]
        
        if board[i][j] == 'R':
            R = (i, j)
        elif board[i][j] == 'B':
            B = (i, j)
        elif board[i][j] == 'O':
            EXIT = (i, j)
 
# N, E, S, W
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
 
 
def solution():
    # BSF
    q = Queue()
    q.put((R, B, 0))
    visited = dict()
    
    while q.qsize() > 0:
        red, blue, count = q.get()
        
        # termination condition
        if count > 10:
            return -1
        
        for dr, dc in directions:
            # move blue ball
            dist_blue = 0
            next_blue = blue
            while board[next_blue[0] + dr][next_blue[1] + dc] != 'O' and board[next_blue[0] + dr][next_blue[1] + dc] != '#':
                next_blue = (next_blue[0] + dr, next_blue[1] + dc)
                dist_blue += 1
                
            # move red ball
            dist_red = 0
            next_red = red
            while board[next_red[0] + dr][next_red[1] + dc] != 'O' and board[next_red[0] + dr][next_red[1] + dc] != '#':
                next_red = (next_red[0] + dr, next_red[1] + dc)
                dist_red += 1
            
            # blue ball is out
            if board[next_blue[0] + dr][next_blue[1] + dc] == 'O':
                continue
            elif board[next_red[0] + dr][next_red[1] + dc] == 'O':
                return count + 1
            
            # if the balls are at the same position
            if next_blue == next_red:
                if dist_red > dist_blue:
                    next_red = (next_red[0] - dr, next_red[1] - dc)
                elif dist_red < dist_blue:
                    next_blue = (next_blue[0] - dr, next_blue[1] - dc)
            
            # prevent count from being over 10
            if count == 10:
                return -1
            
            if (next_red, next_blue) not in visited:
                q.put((next_red, next_blue, count + 1))
        visited[(red, blue)] = True
    return -1
 
 
print(solution())