[BOJ/python] 13460번 구슬 탈출 2

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

13460번: 구슬 탈출 2

문제 해석

 

중력을 이용해 상하좌우로 보드판을 기울여 빨간 구슬을 구멍에 10번 안에 넣는 경우를 구하는 문제이다.

이때 파란구슬이 먼저 구멍에 들어가거나, 동시에 들어가지 않고, 빨간 구슬만 구멍에 먼저 들어가야한다.

---

코드

 

# BOJ 13460

from collections import deque

n, m = map(int,input().split())
arr = []

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
ans = []
t = 10
visit = [[[[[0] * 5 for _ in range(t)] for _ in range(t)] for _ in range(t)] for _ in range(t)]

# Input / 초기 구슬 좌표 저장
for i in range(n):
    arr.append(list(input()))
    for j in range(m):
        if arr[i][j] == 'R': rx, ry = i, j
        elif arr[i][j] == 'B': bx, by = i, j

arr[rx][ry] = '.'
arr[bx][by] = '.'




def selectBeads(rx, ry, bx, by, dir):
    # 상하좌우
    if dir == 0: # 상
        if rx > bx: return bx, by, rx, ry, 'B', 'R'
        else: return rx, ry, bx, by, 'R', 'B'
    elif dir == 1: # 하
        if rx > bx: return rx, ry, bx, by, 'R', 'B'
        else: return bx, by, rx, ry, 'B', 'R'
    elif dir == 2: # 좌
        if ry > by: return bx, by, rx, ry, 'B', 'R'
        else: return rx, ry, bx, by, 'R', 'B'
    else: # 우
        if ry > by: return rx, ry, bx, by, 'R', 'B'
        else: return bx, by, rx, ry, 'B', 'R'

def tilt(rx, ry, bx, by, dir):
    # 일단 구슬 치우고
    arr[rx][ry], arr[bx][by] = '.', '.'
    if dir == 0: # 상
        fx, fy, sx, sy, color1, color2 = selectBeads(rx, ry, bx, by, dir)

        while 1:
            x, y = fx + dx[dir], fy + dy[dir]
            if arr[x][y] == '.':
                fx, fy = x, y
            elif arr[x][y] == 'O':
                fx, fy = color1, color1  # 공이 들어간 경우
                break
            else:
                arr[fx][fy] = color1
                break

        while 1:
            x, y = sx + dx[dir], sy + dy[dir]
            if arr[x][y] == '.':
                sx, sy = x, y
            elif arr[x][y] == 'O':
                sx, sy = color2, color2  # 공이 들어간 경우
                break
            else:
                arr[sx][sy] = color2
                break

    elif dir == 1: # 하
        fx, fy, sx, sy, color1, color2 = selectBeads(rx, ry, bx, by, dir)

        while 1:
            x, y = fx + dx[dir], fy + dy[dir]
            if arr[x][y] == '.':
                fx, fy = x, y
            elif arr[x][y] == 'O':
                fx, fy = color1, color1  # 공이 들어간 경우
                break
            else:
                arr[fx][fy] = color1
                break

        while 1:
            x, y = sx + dx[dir], sy + dy[dir]
            if arr[x][y] == '.':
                sx, sy = x, y
            elif arr[x][y] == 'O':
                sx, sy = color2, color2  # 공이 들어간 경우
                break
            else:
                arr[sx][sy] = color2
                break

    elif dir == 2: # 좌
        fx, fy, sx, sy, color1, color2 = selectBeads(rx, ry, bx, by, dir)

        while 1:
            x, y = fx + dx[dir], fy + dy[dir]
            if arr[x][y] == '.':
                fx, fy = x, y
            elif arr[x][y] == 'O':
                fx, fy = color1, color1  # 공이 들어간 경우
                break
            else:
                arr[fx][fy] = color1
                break

        while 1:
            x, y = sx + dx[dir], sy + dy[dir]
            if arr[x][y] == '.':
                sx, sy = x, y
            elif arr[x][y] == 'O':
                sx, sy = color2, color2  # 공이 들어간 경우
                break
            else:
                arr[sx][sy] = color2
                break
    else: # 우
        fx, fy, sx, sy, color1, color2 = selectBeads(rx, ry, bx, by, dir)

        while 1:
            x, y = fx + dx[dir], fy + dy[dir]
            if arr[x][y] == '.':
                fx, fy = x, y
            elif arr[x][y] == 'O':
                fx, fy = color1, color1  # 공이 들어간 경우
                break
            else:
                arr[fx][fy] = color1
                break

        while 1:
            x, y = sx + dx[dir], sy + dy[dir]
            if arr[x][y] == '.':
                sx, sy = x, y
            elif arr[x][y] == 'O':
                sx, sy = color2, color2  # 공이 들어간 경우
                break
            else:
                arr[sx][sy] = color2
                break

    # for k in arr:
    #     print(*k)
    # print()
    if not(fx == 'R' or fx == 'B'): arr[fx][fy] = '.'
    if not(sx == 'R' or sx == 'B'): arr[sx][sy] = '.'
    if color1 == 'R': return fx, fy, sx, sy
    else: return sx, sy, fx, fy

def bfs(rx, ry, bx, by):
    q = deque()
    q.append((rx, ry, bx, by, 4))
    while q:
        rrx, rry, bbx, bby, d = q.popleft()
        for dir in range(4):
            rx, ry, bx, by = tilt(rrx, rry, bbx, bby, dir)
            if bx == 'B':
                continue
            if rx == 'R':
                return visit[rrx][rry][bbx][bby][d] + 1
            if visit[rx][ry][bx][by][dir] >= 10: return -1
            if visit[rx][ry][bx][by][dir] >= 1: continue

            q.append((rx, ry, bx, by, dir))
            visit[rx][ry][bx][by][dir] = visit[rrx][rry][bbx][bby][d] + 1
    return -1

print(bfs(rx, ry, bx, by))

---

문제 풀이

 

적절히 게임 규칙을 구현하고, BFS를 통해 문제를 해결했다.

 

방문노드 즉, visit 배열을 10 * 10 * 10 * 10 * 5 크기로 만들어 주었다.

순서대로 빨간구슬, 파란구슬의 x y 좌표, 방향을 의미한다.

이를 통해 구슬의 위치가 중복되고, 방향이 중복될 경우 큐에 넣지 않아 중복을 방지하도록 하였고, 이 방문 노드를 통해 기울이기 횟수 또한 셀 수 있도록 만들어 주었다.

 

bfs 종료 조건은 방문 노드의 값 즉 기울이기 횟수가 10회 이상이라면 종료하도록 만들어 주었다.

tilt 함수를 통해 방향에 따른 기울이기 결과의 구슬들의 좌표를 rx, ry, bx, by에 저장하였다.

만약 파란 구슬이 구멍에 들어간 경우 bx, by에 'B' 값을 return해주어 bx값이 B라면 실패한 경우이기 때문에 해당 경우는 큐에 넣지 않도록 하였고,

빨간 구슬만이 구멍에 들어간 경우 이전 방문노드의 값 + 1 을 return하여 출력해주었다.

그외에 중복된 경우 또한 continue를 통해 큐에 들어가지 않도록 해주었다.

 

def selectBeads(rx, ry, bx, by, dir):
    # 상하좌우
    if dir == 0: # 상
        if rx > bx: return bx, by, rx, ry, 'B', 'R'
        else: return rx, ry, bx, by, 'R', 'B'
    elif dir == 1: # 하
        if rx > bx: return rx, ry, bx, by, 'R', 'B'
        else: return bx, by, rx, ry, 'B', 'R'
    elif dir == 2: # 좌
        if ry > by: return bx, by, rx, ry, 'B', 'R'
        else: return rx, ry, bx, by, 'R', 'B'
    else: # 우
        if ry > by: return rx, ry, bx, by, 'R', 'B'
        else: return bx, by, rx, ry, 'B', 'R'

해당 함수는 중력에 따라 먼저 움직일 구슬을 선택해주는 함수이다.

위로 기울였을때는 더 위에 있는 구슬이 먼저 움직이고, 우측으로 기울였을 때는 더 우측에 있는 구슬이 먼저 움직여야 한다.

따라서 해당 구슬의 좌표를 순서대로 return 해주고, 구슬의 색을 순서대로 반환해준다.

 

def tilt(rx, ry, bx, by, dir):
    # 일단 구슬 치우고
    arr[rx][ry], arr[bx][by] = '.', '.'
    if dir == 0: # 상
        fx, fy, sx, sy, color1, color2 = selectBeads(rx, ry, bx, by, dir)

        while 1:
            x, y = fx + dx[dir], fy + dy[dir]
            if arr[x][y] == '.':
                fx, fy = x, y
            elif arr[x][y] == 'O':
                fx, fy = color1, color1  # 공이 들어간 경우
                break
            else:
                arr[fx][fy] = color1
                break

        while 1:
            x, y = sx + dx[dir], sy + dy[dir]
            if arr[x][y] == '.':
                sx, sy = x, y
            elif arr[x][y] == 'O':
                sx, sy = color2, color2  # 공이 들어간 경우
                break
            else:
                arr[sx][sy] = color2
                break

    elif dir == 1: # 하
        fx, fy, sx, sy, color1, color2 = selectBeads(rx, ry, bx, by, dir)

        while 1:
            x, y = fx + dx[dir], fy + dy[dir]
            if arr[x][y] == '.':
                fx, fy = x, y
            elif arr[x][y] == 'O':
                fx, fy = color1, color1  # 공이 들어간 경우
                break
            else:
                arr[fx][fy] = color1
                break

        while 1:
            x, y = sx + dx[dir], sy + dy[dir]
            if arr[x][y] == '.':
                sx, sy = x, y
            elif arr[x][y] == 'O':
                sx, sy = color2, color2  # 공이 들어간 경우
                break
            else:
                arr[sx][sy] = color2
                break

    elif dir == 2: # 좌
        fx, fy, sx, sy, color1, color2 = selectBeads(rx, ry, bx, by, dir)

        while 1:
            x, y = fx + dx[dir], fy + dy[dir]
            if arr[x][y] == '.':
                fx, fy = x, y
            elif arr[x][y] == 'O':
                fx, fy = color1, color1  # 공이 들어간 경우
                break
            else:
                arr[fx][fy] = color1
                break

        while 1:
            x, y = sx + dx[dir], sy + dy[dir]
            if arr[x][y] == '.':
                sx, sy = x, y
            elif arr[x][y] == 'O':
                sx, sy = color2, color2  # 공이 들어간 경우
                break
            else:
                arr[sx][sy] = color2
                break
    else: # 우
        fx, fy, sx, sy, color1, color2 = selectBeads(rx, ry, bx, by, dir)

        while 1:
            x, y = fx + dx[dir], fy + dy[dir]
            if arr[x][y] == '.':
                fx, fy = x, y
            elif arr[x][y] == 'O':
                fx, fy = color1, color1  # 공이 들어간 경우
                break
            else:
                arr[fx][fy] = color1
                break

        while 1:
            x, y = sx + dx[dir], sy + dy[dir]
            if arr[x][y] == '.':
                sx, sy = x, y
            elif arr[x][y] == 'O':
                sx, sy = color2, color2  # 공이 들어간 경우
                break
            else:
                arr[sx][sy] = color2
                break

    # for k in arr:
    #     print(*k)
    # print()
    if not(fx == 'R' or fx == 'B'): arr[fx][fy] = '.'
    if not(sx == 'R' or sx == 'B'): arr[sx][sy] = '.'
    if color1 == 'R': return fx, fy, sx, sy
    else: return sx, sy, fx, fy

해당 함수는 기울였을때, 빨간 구슬과 파란 구슬의 좌표를 반환해주는 함수이다.

dir로 기울이기 방향을 입력받는다.

먼저 원활한 이동을 위해 arr에 존재하는 R과 B는 모두 .으로 바꾸어 준다.

 

이후 selectBeads 함수를 통해 먼저 움직일 구슬의 좌표를 입력받는다.

해당 구슬을 정해진 방향으로 이동 가능하다면 (.) 인경우 계속 이동해준다.

만약 구멍을 만난다면 해당 구슬의 좌표를 구슬의 색으로 지정해준다.

벽이나 구슬을 만난다면 이동하지않고 해당 위치에 구슬을 만들어 놓는다. ( arr[][] = color)

 

두번째 구슬 또한 같은 매커니즘으로 구슬을 이동시킨다. 이 경우에는 먼저 이동한 구슬이 길을 막을 경우가 생기기 때문에 해당 경우도 고려하여 구현해 주었다.

 

fx, fy, sx, sy에는 구슬이 구멍에 들어갔다면 들어간 구슬의 색이 저장되어 있고, 들어가지 않았다면 구슬의 좌표가 저장되어 있다.

좌표가 저장된 경우 해당 좌표의 구슬을 다시 . 으로 바꾸어 주어 다음 이동을 원활하게 한다.

이후 해당 좌표를 모두 return해준다.

 

 

return된 좌표는 구슬이 구멍에 들어간 경우, 즉 B나 R의 값이 있다면 구슬의 색에 따라 예외처리를 해주어 정상적으로 BFS가 돌아가도록 하였다.