[백준/BOJ] #13460 구슬 탈출 2.python(파이썬)

문제 링크 / 출처

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

13460번: 구슬 탈출 2

 

문제 요약

판을 기울여 빨간구슬을 구멍으로 빼낼 때 걸리는 최소횟수를 구하는 문제

[제약사항]

• 3 ≤ N, M ≤ 10

10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력

 

풀이

가능한 모든 경우를 고려하면서 백트래킹을 하기 위해 재귀함수를 사용했다.

 

• 최소횟수를 구해야하므로 지금 시행하려는 횟수가 최소횟수보다 크거나,
• 시행 후에도 두 공 모두 움직임이 없거나,
• 파란공이 구멍으로 빠졌을 떄에는 실행하지 않는 것으로 구현했다.

while문을 이용하여 각 공들이 끝까지 이동할 수 있도록 구현했으며,

 

빨간공과 파란공이 서로의 움직임에 영향을 주므로 같은 while문으로 구성해 동시에 한칸한칸씩 움직이도록 했다.

 

파이참의 디버그 모드를 활용하여 움직임을 직관적으로 볼 수 있었다.

 

코드

# 구슬 탈출 2

def escape(R_now, B_now, cnt):
    global min_cnt
    if cnt >= min_cnt:    # 최소 반복횟수보다 작거나 같은 경우만 계산
        return
    # 시작 위치
    Rr, Rc = R_now
    Br, Bc = B_now

    for i in range(4):
        dr, dc = drc[i]
        flag_success, flag_fail = False, False
        nRr, nRc = Rr, Rc
        nBr, nBc = Br, Bc
        while True:
            # 빨간 공 이동
            if not flag_success and board[nRr + dr][nRc + dc] == '.' or board[nRr + dr][nRc + dc] == 'O':
                R_flag = True
                board[nRr][nRc] = '.'
                nRr += dr
                nRc += dc
                if board[nRr][nRc] == 'O':
                    flag_success = True
                else:
                    board[nRr][nRc] = 'R'
            else:
                R_flag = False

            # 파란 공 이동        
            if not flag_fail and board[nBr + dr][nBc + dc] == '.' or board[nBr + dr][nBc + dc] == 'O':
                board[nBr][nBc] = '.'
                B_flag = True
                nBr += dr
                nBc += dc
                if board[nBr][nBc] == 'O':
                    flag_fail = True
                else:
                    board[nBr][nBc] = 'B'
            else:
                B_flag = False

            if not (R_flag or B_flag):
                break

        # 도착 위치
        R_next = (nRr, nRc)
        B_next = (nBr, nBc)

        if R_now == R_next and B_now == B_next:     # 시작 위치와 도착 위치가 같으면 더이상 진행하지 않음
            continue

        if flag_success and not flag_fail:          # 파란공이 구멍에 들어가지 않고 빨간공만 들어갔을 때
            min_cnt = cnt

        if not flag_fail:                           # 파란공이 구멍에 들어가지 않은 경우에만 추가로 조작함      
            escape(R_next, B_next, cnt + 1)

        # 재귀에서 나온 후 복구
        board[nRr][nRc] = '.'
        board[nBr][nBc] = '.'
        board[Rr][Rc] = 'R'
        board[Br][Bc] = 'B'
        board[Or][Oc] = 'O'


N, M = map(int, input().split())
board = [list(input()) for _ in range(N)]
drc = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# 빨간공, 파란공 위치 찾기
for r in range(N):
    for c in range(M):
        if board[r][c] == 'R':
            R_now = (r, c)
        elif board[r][c] == 'B':
            B_now = (r, c)
        elif board[r][c] == 'O':
            Or, Oc = r, c
min_cnt = 11
escape(R_now, B_now, 1)
print(min_cnt if min_cnt < 11 else -1)