13460 - 구슬 탈출 2

 

---

 

문제

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

13460번: 구슬 탈출 2

 

풀이

아무리봐도 너무 삽질처럼 푼 거 같아 풀이이후에 검색해보니 대부분 bfs 방식으로 문제를 풀었더라.

나만 dfs로 하드하게 풀었다...

 

나 같은 경우에는 이동하기전에 이동경로에 다른 볼이 있는지 먼저 검사했다.

B...R.. 같은 경우나 BR.. 같은 경우등을 고려한 조건이었고, 빨간 구슬을 기준으로 경로에 파란 구슬이 있다면,

파란 구슬을 먼저 이동시킨후에, 빨간구슬을 이동시켰다.

 

이후에는 포멀하게 이동시키는 루틴을 실행시켰고, 만약 파란 구슬이 빠졌을 경우에는 다른 방향으로 다시 시도했다.

문제 풀이 초반에는 파란구슬이 빠지는경우 바로 return 해버렸는데, 다른 경우를 필히 살펴봐야하기 때문에 return 하면 안된다. 단 빨간구슬만 빠지는 경우에는 최솟값을 갱신해주고 바로 return 해주면 된다.

 

또한 분기를 쳐내기 위하여 내가 온 경로로는 다시 안가도록 만들었고, 초기 위치에서 두 구슬 모두가 이동하지 않았더라면 dfs를 실행하지 않도록 구성하였다.

 

코드

import sys
import copy
from sys import stdin

answer = sys.maxsize

def getFromWay(val):
    if val == 0: return 1
    if val == 1: return 0
    if val == 2: return 3
    if val == 3: return 2
    return -1

def isBlueFirst(board, x, y, i):
    global dx, dy
    while True:
        if board[x][y] == 'B':
            return True
        if board[x][y] == '#':
            return False

        x += dx[i]
        y += dy[i]

def dfs(origin, red, blue, way, count):
    global dx, dy, answer

    # 횟수가 10번이 넘어가면 return
    if count > 10:
        return

    # 4방향 모두 굴려본다.
    for i in range(4):
        # 온곳으로 되돌아갈 필요는 없다.
        if i == getFromWay(way): continue
        board = copy.deepcopy(origin)

        rx = red[0] + dx[i]
        ry = red[1] + dy[i]

        bx = blue[0] + dx[i]
        by = blue[1] + dy[i]

        r_possible = False
        b_possible = False


        # 빨간색 구슬이 이동할려는 위치에 파란 구슬이 있다면 -> 파란구슬부터 이동시켜준다.
        if isBlueFirst(board, rx, ry, i):

            # 파란구슬 이동처리
            while True:
                if board[bx][by] == '#':
                    board[blue[0]][blue[1]] = '.'
                    before = getFromWay(i)
                    bx = bx + dx[before]
                    by = by + dy[before]
                    board[bx][by] = 'B'
                    break
                elif board[bx][by] == 'O':
                    board[blue[0]][blue[1]] = '.'
                    b_possible = True
                    break

                bx = bx + dx[i]
                by = by + dy[i]

            # 빨간구슬 이동처리
            while True:
                if board[rx][ry] == '#' or board[rx][ry] == 'B':
                    board[red[0]][red[1]] = '.'
                    before = getFromWay(i)
                    rx = rx + dx[before]
                    ry = ry + dy[before]
                    board[rx][ry] = 'R'
                    break
                elif board[rx][ry] == 'O':
                    board[red[0]][red[1]] = '.'
                    r_possible = True
                    break

                rx = rx + dx[i]
                ry = ry + dy[i]

            # 안됐을 시, 되돌려 준 후에, 남은 방향들을 탐색해봐야한다.
            if b_possible:
                continue

            # 됐을경우에는 바로 return한다.
            if r_possible:
                answer = min(answer, count)
                return

        # 빨간구슬부터 움직인다.
        else:
            # 빨간구슬 이동처리
            while True:
                if board[rx][ry] == '#':
                    board[red[0]][red[1]] = '.'
                    before = getFromWay(i)
                    rx = rx + dx[before]
                    ry = ry + dy[before]
                    board[rx][ry] = 'R'
                    break
                if board[rx][ry] == 'O':
                    board[red[0]][red[1]] = '.'
                    r_possible = True
                    break

                rx = rx + dx[i]
                ry = ry + dy[i]

            # 파란구슬 이동처리
            while True:
                if board[bx][by] == '#' or board[bx][by] == 'R':
                    board[blue[0]][blue[1]] = '.'
                    before = getFromWay(i)
                    bx = bx + dx[before]
                    by = by+ dy[before]
                    board[bx][by] = 'B'
                    break
                if board[bx][by] == 'O':
                    board[blue[0]][blue[1]] = '.'
                    b_possible = True
                    break

                bx = bx + dx[i]
                by = by + dy[i]

            # 안됐을 시, 되돌려 준 후에, 남은 방향들을 탐색해봐야한다.
            if b_possible:
                continue

            # 됐을시에도 바로 return 하지 말고, 남은 방향들을 탐색해봐야한다.
            if r_possible:
                answer = min(answer, count)
                return

        # 아무 이동도 없다면 depth를 늘려주지 말고, 다른 방향으로 바로 돌려주면 된다.
        if red[0] == rx and red[1] == ry and blue[0] == bx and blue[1] == by:
            continue

        dfs(board, (rx, ry), (bx, by), i, count+1)

# Initialize
n, m = map(int, input().split())
original = [list(stdin.readline().rstrip()) for _ in range(n)]

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

r_position = 0
b_position = 0
for x in range(n):
    for y in range(m):
        if original[x][y] == 'R':
            r_position = (x, y)
        if original[x][y] == 'B':
            b_position = (x, y)

dfs(original, r_position, b_position, -1, 1)

print(answer) if answer != sys.maxsize else print(-1)

 

후기

 

-

이동 부분에 있어서 코드가 심히 중복된다. 

다른 코드들을 참고해보니, 구슬들의 순서를 기억한 후에 그와 상관없이 일단 이동시켰다. 

그리고 같은 위치에 존재할경우 , 기존 구슬 순서를 참고해 재정렬 시켜줬더라.

 

-

나도 최대한 함수를 구현하는 식으로, 코드를 분리하고 중복을 제거하는 방식으로 짤 수 있도록 노력해야겠다.

그렇게 해야지 디버깅도 편할 뿐더러, 테스트를 위하여 일정 구조를 바꿀때도 편한 거 같다. 

 

-

무지성으로 구현을 빡! 할수도 있으나.. 어떤 자료구조를 쓰면 좋을지도 조금은 더 고민해보자. 너무 생각나는대로 코드를 작성했던 거 같다.