1. 문제

📌문제 보러 가기!

2. 접근법

1. rolling 함수를 정의한다.

def rolling(graph, x, y, xx, yy, direction):
	# x, y는 현재 체크할 구슬의 현재 좌표이고, xx와 yy는 나머지 구슬의 현재 좌표이다
	# direction은 0 ~ 3 중 한 가지가 입력되며 상, 하, 좌, 우를 의미한다
    m = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    dx, dy = m[direction]
    # 가는 경로에 다른 구슬이 존재하는지 체크
    flag = False

	# 반복문을 통해 벽에 닿을 때까지 이동한다
    while True:
        x += dx
        y += dy
        # 벽을 만나면 좌표 return
        # False는 구멍에 빠지지 않았다는 의미
        if graph[x][y] == '#':
        	# 가는 경로에 다른 구슬이 있었으면, 현재 좌표에서 dx, dy를 두 번 빼 준다
            if flag:
                return False, x - (2 * dx), y - (2 * dy)
            else:
                return False, x - dx, y - dy
        # 'O'(구멍)을 만나면 True를 return
        elif graph[x][y] == 'O':
            return True, x, y
        # 가는 경로에 다른 구슬이 있으면 flag를 True로 바꾼다
        elif (x, y) == (xx, yy):
            flag = True

2. N과 M을 입력받고 전체 그래프를 2차원 배열로 입력받는다.

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

for i in range(N):
    graph.append(list(input()))
    for j in range(M):
    	# 빨간 구슬과 파란 구슬의 위치를 찾아 rx, ry, bx, by에 저장하고,
        # graph의 해당 부분을 '.'으로 변경하여 구슬이 없는 그래프를 만든다.
        if graph[i][j] == 'R':
            rx, ry = i, j
            graph[i][j] = '.'
        elif graph[i][j] == 'B':
            bx, by = i, j
            graph[i][j] = '.'

3. bfs를 진행한다. 이때, heapq를 사용하여 count 값이 가장 적은 순서대로 pop되도록 한다.
   visited를 통해 중복 이동을 방지한다. defaultdict를 사용하여 빨간 구슬과 파란 구슬 해당 좌표에 동시에 존재한 적이 있는지 체크한다.

q = [(1, rx, ry, bx, by)]
heapq.heapify(q)
visited[(rx, ry, bx, by)] = True

while q:
    cnt, rx, ry, bx, by = heapq.heappop(q)

    if cnt > 10:
        print(-1)
        exit()

    for i in range(4):
        rtf, nrx, nry = rolling(graph, rx, ry, bx, by, i)
        btf, nbx, nby = rolling(graph, bx, by, rx, ry, i)
        # 해당 좌표에 존재한 적 있으면 continue
        if visited[(nrx, nry, nbx, nby)]:
            continue
        # 파란 구슬이 구멍으로 빠지는 경우 continue
        if btf:
            continue
        # 파란 구슬은 빠지지 않고, 빨간 구슬만 빠지는 경우 count 값을 return
        elif rtf:
            print(cnt)
            exit()
        # 둘 다 구멍으로 빠지지 않았을 경우 큐에 추가한다.
        else:
            heapq.heappush(q, (cnt + 1, nrx, nry, nbx, nby))
            visited[(nrx, nry, nbx, nby)] = True


print(-1)

3. 전체 코드

import heapq
from collections import defaultdict


def rolling(graph, x, y, xx, yy, direction):
    m = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    dx, dy = m[direction]
    flag = False

    while True:
        x += dx
        y += dy
        if graph[x][y] == '#':
            if flag:
                return False, x - (2 * dx), y - (2 * dy)
            else:
                return False, x - dx, y - dy
        elif graph[x][y] == 'O':
            return True, x, y
        elif (x, y) == (xx, yy):
            flag = True


N, M = map(int, input().split())
graph = []
visited = defaultdict(bool)
rx, ry, bx, by = 0, 0, 0, 0

for i in range(N):
    graph.append(list(input()))
    for j in range(M):
        if graph[i][j] == 'R':
            rx, ry = i, j
            graph[i][j] = '.'
        elif graph[i][j] == 'B':
            bx, by = i, j
            graph[i][j] = '.'

q = [(1, rx, ry, bx, by)]
heapq.heapify(q)
visited[(rx, ry, bx, by)] = True

while q:
    cnt, rx, ry, bx, by = heapq.heappop(q)

    if cnt > 10:
        print(-1)
        exit()

    for i in range(4):
        rtf, nrx, nry = rolling(graph, rx, ry, bx, by, i)
        btf, nbx, nby = rolling(graph, bx, by, rx, ry, i)
        if visited[(nrx, nry, nbx, nby)]:
            continue
        if btf:
            continue
        elif rtf:
            print(cnt)
            exit()
        else:
            heapq.heappush(q, (cnt + 1, nrx, nry, nbx, nby))
            visited[(nrx, nry, nbx, nby)] = True


print(-1)