[백준 BOJ] 13460 구슬 탈출 2 (python)

문제 출처 : https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

🔥 작성 코드

def sol(rsi, rsj, bsi, bsj, cnt):
    global result

    # 최소값이 아니라면 종료
    if result <= cnt:
        return

    # 기울인 횟수가 10번이 넘어가면 종료
    if cnt > 10:
        return

    # 4방향으로 기울이기
    for d in range(4):
        flag = 0
        rni = rsi + di[d]
        rnj = rsj + dj[d]
        bni = bsi + di[d]
        bnj = bsj + dj[d]
        if arr[rni][rnj] != '#' or arr[bni][bnj] != '#':
            # d방향으로 기울였을 때 빨간 구슬 위치
            dist1 = 0
            for c in range(1, N+M):
                rni = rsi + c*di[d]
                rnj = rsj + c*dj[d]
                if arr[rni][rnj] == '#':
                    break
                elif arr[rni][rnj] == 'O':
                    flag = 1
                    break
                elif rni == bsi and rnj == bsj:
                    continue
                else:
                    dist1 += 1
            rni = rsi + dist1*di[d]
            rnj = rsj + dist1*dj[d]

            # d방향으로 기울였을 때 파란 구슬 위치
            dist2 = 0
            for c in range(1, N+M):
                bni = bsi + c*di[d]
                bnj = bsj + c*dj[d]
                if arr[bni][bnj] == '#':
                    break
                elif arr[bni][bnj] == 'O':
                    flag = 2
                    break
                elif flag==0 and bni == rsi and bnj == rsj:
                    continue
                else:
                    dist2 += 1

            # 파란 구슬이 들어간 경우 실패
            if flag == 2:
                continue

            # 빨간 구슬만 들어간 경우 성공
            if flag == 1:
                result = cnt
                return

            # 이동한 위치에서 다시 한 번 기울이기
            bni = bsi + dist2*di[d]
            bnj = bsj + dist2*dj[d]

            # 처음 위치와 동일하면 제외
            if rsi == rni and rsj == rnj and bsi == bni and bsj == bnj:
                continue
            sol(rni, rnj, bni, bnj, cnt+1)


di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]

N, M = map(int, input().split())

arr = [list(input()) for _ in range(N)]

for i in range(N):
    for j in range(M):
        if arr[i][j] == 'R':
            rsi = i
            rsj = j
        elif arr[i][j] == 'B':
            bsi = i
            bsj = j

result = 11
sol(rsi, rsj, bsi, bsj, 1)

if result == 11:
    result = -1

print(result)

 

⭕ 해설

• 구슬의 좌표만 고려하였습니다.
• 주어진 첫 좌표부터 상, 하, 좌, 우로 기울이는 함수를 호출합니다.
• 기울였을 때 두 구슬 중 하나라도 이동이 가능하다면 기울입니다. (해당 방향을 벽이 막고있지 않다면)
• dist1과 dist2를 이용하여 빨간 구슬과 파란 구슬의 이동거리를 구하였습니다.
• 만약 파란구슬이 탈출했다면 실패, 빨간 구슬만 탈출했다면 cnt를 결과값으로 저장합니다.
  • cnt가 이미 저장된 결과값보다 클 경우 반환하였으므로 대소비교 필요x
• 10번 기울여도 빨간구슬만 탈출하는 경우가 없다면 -1을 출력합니다.