13460_구슬탈출 2

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

13460번: 구슬 탈출 2

 

 

삼성역량 테스트 문제였다고 한다. 

 

예시에 있을법한 반례들이 거의 다 주어져서 그런지 시간은 조금 걸렸지만 도움을 안받고 스스로 푸는데에는 성공했다.

 

 

문제를 접근하는 것은 간단했는데 꼼꼼하게 체크하는것이 중요했다. 전체적인 흐름은 아래와 같다.

 

 

1. R,B,O의 좌표를 처음 가지고 시작

2. 큐를 활용하여 bfs 탐색 (상하좌우)

3. B가 O위치에 있다면 탐색을 넘어가서 다음 큐를 검사하고, R이 O위치에 있다면 종료

4. 상하좌우를 검색하면서 #이 아니면 큐에 추가

5. 11번 이상 검색시 종료

 

전체적인 흐름은 위와 같지만 여러 반례들을 꼼꼼히 생각하면서 풀어야한다. 생각할만한 것들은 아래와 같다.

 

1. R,B가 동시에 도착하는 경우 --> B를 먼저 검사해서 해결

2. R,B가 동시에 겹치는 경우 --> 도착지가 아니라면 먼저 간것 뒤에 쌓이게 한다.

3. 카운트 세는법 --> 큐에 넣을때 cnt를 넣어서 활용

 

import sys
from collections import deque
input = sys.stdin.readline

n,m = map(int,input().split())

dx = [ 1,0,-1,0 ]
dy = [ 0,1,0,-1 ]

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

R_co,O_co,B_co = [],[],[]
for i in range(n):  
    for j in range(m):
        if board[i][j] == 'R':
            R_co = [i,j]
        elif board[i][j] == 'B':
            B_co = [i,j]
        elif board[i][j] == 'O':
            O_co = [i,j]

q = deque([ [R_co,B_co,0] ])

while q:
    R,B,cnt = q.popleft()

    if cnt > 10:
        print(-1)
        break
    if B == O_co:
        continue
    elif R == O_co:
        print(cnt)
        break

    for i in range(4):
        # print(R, B)
        Rnx,Rny = R[1],R[0]
        while True:
            if board[Rny + dy[i]][Rnx + dx[i]] == '#':
                break
            Rnx,Rny = Rnx + dx[i],Rny + dy[i]
            if board[Rny][Rnx] =='O':
                break


        Bnx, Bny = B[1], B[0]
        while True:
            if board[Bny + dy[i]][Bnx + dx[i]] == '#':
                break
            Bnx, Bny = Bnx + dx[i], Bny + dy[i]
            if board[Bny][Bnx] =='O':
                break

        if Rnx == Bnx and Rny == Bny and board[Bny][Bnx] != 'O':
            if dx[i] == 0:
                if B[0] * dy[i] < R[0] * dy[i]:
                    Bny = Bny - dy[i]
                else:
                    Rny = Rny - dy[i]
            else:
                if B[1] * dx[i] < R[1] * dx[i]:
                    Bnx = Bnx - dx[i]
                else:
                    Rnx = Rnx - dx[i]

        for r,b,c in q:
            if r == [Rny,Rnx] and b == [Bny,Bnx]:
                break
        else:
            q.append([[Rny,Rnx],[Bny,Bnx],cnt+1])