[python3] 백준 14360 풀이 ( 구슬 탈출 2, BFS, 방문체크 없음 )

이번 문제는 저번 주 스터디에서 풀지 못한 문제였는데, 생각할 시간이 상당히 많았기 때문에 겨우 풀었다.

우선 문제를 살펴보자

문제를 요약하면 상하좌우로 움직일 수 있는 판을 가지고 있을 때, 빨간공만을 출구로 뽑아내는 경우 얼마나 시간이 걸리는지 알아내는 문제이다. 이때 한 방향으로 움직이는 경우 두 공이 못 움직일 때까지 움직인다.

우선 우리는 최소로 움직여서 공을 뽑아낼 것이다. 즉, 최단 거리나 최단 경우의 수를 구할 때는 역시 BFS를 사용해야한다.

두번째로 우리는 2공(빨강,파랑)을 상하좌우로 움직일 것이다. 움직일 때는 한번에 움직이지 못하고 한 칸씩 이동하면서 움직여야한다. 왜냐하면 그래야 겹치는 경우를 피할 수 있다. 그런데 겹치는 경우를 위해 한 칸씩 움직인다고 한다면 방향에 따라 두 공 중 누가 더 먼저 움직이는지를 정해야 한다. 예를 들어 위로 움직이는 경우 y좌표가 작은 값이 먼저 움직여야한다. 오른쪽으로 움직인다면 x좌표가 큰 쪽이 먼저 움직여야 한다. 이를 정리하면 아래와 같다.

1. 상 : y 좌표가 작은거 부터 이동
2. 하 : y 좌표가 큰거 부터 이동
3. 좌 : x 좌표가 작은거 부터 이동
4. 우 : x 좌표가 큰거 부터 이동

 

세번째로 BFS이기 때문에 visited를 체크할 것인지 고민해본다. 난 처음에 이 부분을 체크해야 한다고 생각했다. 이제까지 BFS를 풀 때 그렇게 풀었고, 중복되는 경우의 수를 피하기 위함이었다. 그런데 이 문제는 visited없이 풀린다. 오히려 visited를 넣으면 풀리지가 않는다. 내가 생각해본 이유는 다음과 같다.

visited_R,visited_B가 있다고 가정하자. 만약 [1,2],[2,4]를 들렀다. 그럼 이 부분이 1로 바뀐다. 이후 [1,3],[2,5]를 들르면 이부분도 1로 바뀐다. 그럼 [1,2],[2,5]는 들르지 않은 경우의 수이다. 그런데 이미 둘 다 1로 바뀌어 있기 때문에 이미 확인한 경우가 되어버린다. 그래서 들르지 않고 끝나버린다. 이렇다 보니 더 나아가야 하는데 나아가지 못하고 잘못된 값을 반환하게 되었다. 그래서 visited를 아예 없애 버린 결과 제출에 성공할 수 있었다. (만약 주어진 N이 더 크다면 다른 방법을 찾아야할 것 같다.)

 

이 3가지를 염두하고 문제를 해결한다면 생각보다 코드를 짜기에는 어렵지 않다. 나도 2가지를 염두하고 문제를 설계하고 코딩을 진행했다. 이후 문제가 풀리지 않아 디버깅 하다 보니 3번째 이슈인 방문 체크를 제거하고 제출했고, 정답을 받을 수 있었다. 

'''
빨강,파랑 같이 움직임, 기울이기는 둘다 안움직일때까지
완전 탐색 해야함 , 최소 횟수로 빠져나와야함. -> BFS

1. 이동방향 정하기
2. 이동시키기 
3. 만약 이동중에 구멍에 볼 들어가면 함수 반환

세부적으로 어떤 공을 먼저 움직이게 할지
상하좌우 방향에 따라 먼저 움직여야 하는 공이 다르다.
1. 상 : y 좌표가 작은거 부터 이동
2. 하 : y 좌표가 큰거 부터 이동
3. 좌 : x 좌표가 작은거 부터 이동
4. 우 : x 좌표가 큰거 부터 이동

=> visited 없으니 통과....?
'''

N,M = map(int, input().split()) # 세로 가로
Map = []
R, B = 0,0
for i in range(N):
    tmp = list(input())
    Map.append(tmp)
    for j in range(M):
        if tmp[j] == "R":
            R = [i,j]
        if tmp[j] == "B":
            B = [i,j]

dy = [-1,1,0,0] # 상하좌우
dx = [0,0,-1,1]

from collections import deque
from time import sleep
def go(direction,R,B):
    b1, b2 = R,B
    reverse = 0
    if direction == [-1,0]:#상
        if R[0] < B[0]:#y가 작으면 그대로
            b1, b2 = R,B
        else:
            b1, b2 = B,R
            reverse = 1
    elif direction == [1,0]:#하
        if R[0] < B[0]:# y가 작으면 반대로
            b1,b2 = B,R
            reverse = 1
        else:
            b1,b2 = R,B
    elif direction == [0,-1]:#좌
        if R[1] < B[1]: # x가 작으면 그대로
            b1,b2 = R,B
        else:
            b1,b2 = B,R
            reverse = 1
    else:#우
        if R[1] < B[1]: # x가 작으면 반대로
            b1,b2 = B,R
            reverse = 1
        else:
            b1,b2 = R,B
    # 본격적으로 값을 밀어본다.
    outdoor1 = False
    outdoor2 = False
    y,x = b1
    while True: # b1을 먼저 움직인다.
        ny = y + direction[0]
        nx = x + direction[1]
        if (0<ny<N-1) and (0<nx<M-1): # 허용 인덱스 범위
            if Map[ny][nx] == "O": # 출구 만남
                y = ny
                x = nx
                outdoor1 = True
                break
            elif Map[ny][nx] != '#': #벽이 아니라면 움직이기 가능
                y = ny
                x = nx
                continue
            else:
                break
        else:
            break
    y2,x2 = b2
    while True: # b2를 움직인다.
        ny2 = y2 + direction[0]
        nx2 = x2 + direction[1]
        if (0<ny2<N-1) and (0<nx2<M-1): # 허용 인덱스 범위
            if Map[ny2][nx2] == "O":
                y2 = ny2
                x2 = nx2
                outdoor2 = True
                break
            elif Map[ny2][nx2] != '#' and [ny2,nx2]!=[y,x]: #벽이 아니거나 앞의 공이 아니면 움직이기 가능
                y2 = ny2
                x2 = nx2
                continue
            else: #갈수 없는경우
                break
        else:
            break
    # 정산시작~ #outdoor가 0이면
    if reverse == 0: # R , B
        if outdoor1==False and outdoor2==False: # 다른방향도 해야함.
            q.append([[y,x],[y2,x2]])
            return 0
        elif outdoor1==True and outdoor2==False:# 성공!
            return 1
    else: # B, R
        if outdoor1==False and outdoor2==False: # 다른방향도 해야함.
            q.append([[y2,x2],[y,x]])
            return 0
        elif outdoor1==False and outdoor2==True:# 성공!
            return 1

def BFS():
    time = 0
    while time < 10:
        time += 1
        for _ in range(len(q)):
            r,b = q.popleft()
            y,x = r
            y2,x2 = b
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                ny2 = y2 + dy[i]
                nx2 = x2 + dx[i]
                # 둘중에 하나라도 움직이는게 가능하면됨
                if ((0<ny<N-1) and (0<nx<M-1)) or ((0<ny2<N-1) and (0<nx2<M-1)):# 인덱스 이동가능
                    if Map[ny][nx] != '#' or Map[ny2][nx2] != '#': # 이동가능
                        if go([dy[i],dx[i]], r,b) == 1: # 어디로 이동할건지, 이동시작하는 r,b좌표보내준다.
                            return time
    return -1
q = deque([[R,B]])
print(BFS())

 

결론 : BFS도 조건 많이 들어가니까 상당히 어렵다. BFS 무시하지 말고 더 어려운 문제 풀어봐야 겠다.