[백준] 13460 - 구슬 탈출 2 (G1)

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

13460번: 구슬 탈출 2

단순 BFS 문제를 구현하기 어렵게 내면 이렇게 나올 수 있다는 걸 보여준 문제이다..

2048과 비슷하게 그냥 상하좌우 이동을 구현하고, 모든 경우의 수를 세면 된다.

 

각 이동마다 가능한 경우의 수가 상하좌우 4방향 이고, 10번을 넘는 이동은 의미가 없으므로

진짜 의미로 모든 경우의 수는 4^10 = 약 100만 의 경우의 수겠지만,

이 경우의 수를 다 세면 시간초과 / 메모리초과가 나온다.

 

그래서 이동하는 과정을 잘 고민하면, 경우의 수를 줄일 수 있다.

바로, 직전에 좌우 이동을 한 경우에는 다음에 상하 이동을 해야하고,

직전에 상하 이동을 한 경우에는 다음에 좌우 이동을 해야 하는 점을 이용한다.

 

그럼 경우의 수가 2^9 * 4 = 2^11 으로 줄어든다.

(맨 처음 이동 방향은 4가지, 이후 9번 남은 이동에 대해 선택가짓수가 2가지이다.)

---

어차피 이 문제의 난이도는 구현에서 치솟기에 이 아이디어를 떠올리기는 힘들지 않았다.

나는 구현을 2048때와 비슷하게 했다.

 

이동에 대한 함수를 아래와 같이 구현하였다.

 

1. "이동방향의 반대방향"으로 각 줄을 순회한다.

2. 구멍을 만나면 이 줄에 구멍이 있음을 표시한다. (플래그 활용)

2. 벽을 만나면 벽의 위치를 갱신한다. 이때 구멍이 있었다면 구멍이 있음을 표시하는 플래그를 끈다.

3. 구슬을 만나면 구슬의 위치를 기존 벽 위치에서 이동방향으로 한번 더간 위치로 갱신하고,

벽의 위치를 구슬의 최종 위치로 갱신한다. (구슬도 다른 구슬에겐 벽이므로)

이때 만약 구멍이 있는 플래그가 켜져있었다면 구슬이 구멍으로 들어갔으므로 구슬의 존재여부 플래그를 끈다.

이때는 벽의 위치가 갱신되지 않는다.

4. 순회를 마친 후 R 구슬만 구멍으로 들어갔다면 "CLEAR" 를 리턴한다.

만약 B 구슬이 들어갔다면 "FAIL" 을 리턴한다.

둘다 들어가지 않았다면 순회 결과를 튜플로 바꾸어 리턴한다.

---

만약 왼쪽으로 이동한다고 하면, 이동할 목적지 (맨 오른쪽)부터 이동시작지점(맨 왼쪽) 으로 순회하면서

벽과 구슬, 구멍을 찾았다.

0 1 2 3 4 5

R . . # . #

 

이 상태에서 오른쪽으로 이동한다고 해보자.

그럼 5번 인덱스부터 거꾸로 왼쪽방향인 0으로 가면서 '#' 을 만날 때마다 벽의 위치를 갱신한다.

그럼 R 인덱스에 도착했을 대 벽의 위치는 3 이므로,

진행 방향에서 한칸 더간 2 위치에 R 구슬을 두고, 기존 R 구슬은 빈공간으로 만든다.

 

. . R # . #

 

결과가 이렇게 나온다.

---

제출 코드는 아래와 같다.

 

from collections import deque
TestMode = False


def move(d, board, n, m):
    result = [list(board[i][:]) for i in range(n)]
    isThereRed = True
    isThereBlue = True
    if d == 'L':
        for i in range(n):
            last_wall = -1
            isThereHole = False
            for j in range(m-1, -1, -1):
                if result[i][j] == '#':
                    last_wall = j
                    isThereHole = False
                elif result[i][j] == 'O':
                    isThereHole = True
                elif result[i][j] == 'R' or result[i][j] == 'B':
                    if isThereHole:
                        if result[i][j] == 'R':
                            isThereRed = False
                        elif result[i][j] == 'B':
                            isThereBlue = False
                    result[i][last_wall-1] = result[i][j]
                    if last_wall-1 != j:
                        result[i][j] = '.'
                    last_wall -= 1
    elif d == 'R':
        for i in range(n):
            last_wall = -1
            isThereHole = False
            for j in range(m):
                if result[i][j] == '#':
                    last_wall = j
                    isThereHole = False
                elif result[i][j] == 'O':
                    isThereHole = True
                elif result[i][j] == 'R' or result[i][j] == 'B':
                    if isThereHole:
                        if result[i][j] == 'R':
                            isThereRed = False
                        elif result[i][j] == 'B':
                            isThereBlue = False
                    result[i][last_wall+1] = result[i][j]
                    if last_wall+1 != j:
                        result[i][j] = '.'
                    last_wall += 1
    elif d == 'U':
        for j in range(m):
            last_wall = -1
            isThereHole = False
            for i in range(n):
                if result[i][j] == '#':
                    last_wall = i
                    isThereHole = False
                elif result[i][j] == 'O':
                    isThereHole = True
                elif result[i][j] == 'R' or result[i][j] == 'B':
                    if isThereHole:
                        if result[i][j] == 'R':
                            isThereRed = False
                        elif result[i][j] == 'B':
                            isThereBlue = False
                    result[last_wall+1][j] = result[i][j]
                    if last_wall+1 != i:
                        result[i][j] = '.'
                    last_wall += 1
    elif d == 'D':
        for j in range(m):
            last_wall = -1
            isThereHole = False
            for i in range(n-1, -1, -1):
                if result[i][j] == '#':
                    last_wall = i
                    isThereHole = False
                elif result[i][j] == 'O':
                    isThereHole = True
                elif result[i][j] == 'R' or result[i][j] == 'B':
                    if isThereHole:
                        if result[i][j] == 'R':
                            isThereRed = False
                        elif result[i][j] == 'B':
                            isThereBlue = False
                    result[last_wall-1][j] = result[i][j]
                    if last_wall-1 != i:
                        result[i][j] = '.'
                    last_wall -= 1

    if TestMode:
        print(d)
        printBoard(board, n)
        print()
        printBoard(result, n)

    if not isThereRed and isThereBlue:
        return 'CLEAR'
    elif isThereRed and isThereBlue:
        return tuple(map(tuple, result))
    else:
        return 'FAIL'


def solve():
    n, m = map(int, input().split())
    board = [list(input()) for _ in range(n)]
    printBoard(board, n)

    answer = -1

    d = deque()
    d.append(('L', 1, move('L', board, n, m)))
    d.append(('R', 1, move('R', board, n, m)))
    d.append(('U', 1, move('U', board, n, m)))
    d.append(('D', 1, move('D', board, n, m)))
    while d:
        last_move, cnt, move_result = d.popleft()
        if move_result == 'FAIL':
            continue
        elif move_result == 'CLEAR':
            answer = cnt
            break

        # cnt = 10 인데 이 코드까지 왔다는 건 클리어를 못했단 소리.
        if cnt == 10:
            continue

        # 직전에 좌/우 로 이동했다면, 그 다음에는 상/하 이동만 의미 있는 이동이다.
        if last_move == 'L' or last_move == 'R':
            d.append(('U', cnt + 1, move('U', move_result, n, m)))
            d.append(('D', cnt + 1, move('D', move_result, n, m)))
        else:
            d.append(('L', cnt + 1, move('L', move_result, n, m)))
            d.append(('R', cnt + 1, move('R', move_result, n, m)))

    print(answer)


def printBoard(board, n):
    if TestMode:
        for i in range(n):
            print(board[i])


if __name__ == "__main__":
    solve()

한가지 반성하는 점은, 코드를 구현하다가 중간에 보드를 이상하게 갱신하는 경우를 발견했는데,

몇 개 넣어본 테케를 정상적으로 출력하길래 문제가 없을 줄 알고 그냥 제출해서 WA를 받았었다.

그래서 스스로 디버깅을 해보다가 안되서 질문게시판의 테스트케이스를 이용해서 해결했었다.

중간에 뭔가 의도와 다르게 작동하는 부분이 있다면, 답이 아무리 제대로 나온다고 해도 꼭 손보는 습관을 가져야겠다.