[백준] 구슬 탈출 2

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

13460번: 구슬 탈출 2

bfs를 사용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

5 5
#####
#..B#
#.#.#
#RO.#
#####

다음과 같이 row, column이 첫줄에, 그리고 이후로는 구슬이 움직이는 공간이 2d array로 주어집니다. 

이 때, 상하 좌우로 구슬을 기울여 빨간 구슬이 빠져나오게 하는 최소 횟수를 구해야 합니다. 이 때, 10번 이하로 빨간 구슬을 빼내지 못하는 경우에는 -1을 출력해야 하고, 파란구슬이 구멍으로 빠져나오는 경우에도 실패합니다. 

실제로 문제를 한번 읽어 보는 것을 추천합니다. 

 

<Solution>

bfs를 이용하여 문제를 해결합니다. 이때 헷갈리를 부분들 몇가지를 정리해 보려 합니다. 

 

1. R, B가 같은 줄에 있는 경우에 대한 이야기

7 7
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######

다음과 같은 상황을 생각해봅시다. 이때, 왼쪽으로 기울이게 되면, R,B의 이동을 어떻게 하면 편하게 생각 할 수 있을까요? R,B를 우선 최대한 왼쪽으로 이동시킨 다음, 각각의 이동 횟수를 기록해둔다음, 만약 이후의 좌표가 똑같은 경우, 더 많이 이동한 구슬을 반대로 한칸 움직이는 형태로 처리하면 간단하게 처리할 수 있습니다. 

 

2. R과 B가 둘다 빠져나가는 경우에 대한 처리

B가 O를 지나는 경우중 정답으로 나올 수 있는 것이 있을지 생각해보면 아무 경우가 없습니다. 둘다 빠져나가는 경우에 대한 처리를 하는 것은 단순히 B가 O를 지나는 경우를 break 시키는 방식으로 처리가 가능합니다. 

 

3. 이미 탐색한 경우의 수를 탐색하지 않게 하는 방법

4D array를 구성해서 True 로 마킹함으로써 처리할 수 있습니다. 

visited = [[[[False]*n for _ in range(m)] for _ in range(n)] for _ in range(m)]
# r_row, r_column, b_row, b_column

 

실제 구현은 아래와 같습니다. 

import sys
from collections import deque

# get 2d array size
m,n = list(map(int,sys.stdin.readline().rstrip().split())) # row, column

# build 2d array
array = []
for i in range(m):
    array.append(list(sys.stdin.readline().rstrip()))

# right down up left
d_row = [0, 1, 0, -1]
d_column = [1, 0, -1, 0]

# find R,B
for i in range(m):
    for j in range(n):
        if array[i][j] == 'R':
            r_pos = [i,j]
            array[i][j] == '.'
        elif array[i][j] == 'B':
            b_pos = [i,j]
            array[i][j] == '.'
        else:
            continue

# build visited array
visited = [[[[False]*n for _ in range(m)] for _ in range(n)] for _ in range(m)]
# r_row, r_column, b_row, b_column

q = deque([[r_pos, b_pos, 0]])
visited[r_pos[0]][r_pos[1]][b_pos[0]][b_pos[1]] = True

while(q):
    r_, b_, time = q.popleft()
    if time > 9:
        break
    for i in range(4):
        r = r_[:]
        b = b_[:]
        # move four direction
        r_c = 0
        b_c = 0
        b_f = 0
        b_f2 = 0
        # move R
        while(1):
            if array[r[0] + d_row[i]][r[1] + d_column[i]] == 'O':
                b_f = 1
                break
            if array[r[0] + d_row[i]][r[1] + d_column[i]] != '#':
                r[0] += d_row[i]
                r[1] += d_column[i]
                r_c += 1
            else:
                break
        # move B
        while(1):
            if array[b[0] + d_row[i]][b[1] + d_column[i]] == 'O':
                b_f2 = 1
                break
            if array[b[0] + d_row[i]][b[1] + d_column[i]] != '#':
                b[0] += d_row[i]
                b[1] += d_column[i]
                b_c += 1
            else:
                break
        if b_f2 == 1:
            continue
        if b_f == 1:
            print(time+1)
            exit()
        # if they are at same position
        if r[0] == b[0] and r[1] == b[1]:
            if r_c > b_c:
                r[0] -= d_row[i]
                r[1] -= d_column[i]
            else:
                b[0] -= d_row[i]
                b[1] -= d_column[i]
        # if visited? 
        if visited[r[0]][r[1]][b[0]][b[1]] == True:
            continue
        else:
            visited[r[0]][r[1]][b[0]][b[1]] = True
            q.append([[r[0],r[1]], [b[0],b[1]], time+1])

print(-1)