[파이썬] 13460. 구슬 탈출 2

문제

스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

예제 입력 1 

5 5
#####
#..B#
#.#.#
#RO.#
#####

예제 출력 1 

1

예제 입력 2 

7 7
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######

예제 출력 2 

5

예제 입력 3 

7 7
#######
#..R#B#
#.#####
#.....#
#####.#
#O....#
#######

예제 출력 3 

5

예제 입력 4 

10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.#.#..#
#...#.O#.#
##########

예제 출력 4 

-1

예제 입력 5 

3 7
#######
#R.O.B#
#######

예제 출력 5 

1

예제 입력 6 

10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.##...#
#O..#....#
##########

예제 출력 6 

7

예제 입력 7 

3 10
##########
#.O....RB#
##########

예제 출력 7 

-1

 

 

🐩 나의 풀이

import sys
from collections import deque
import copy

input=sys.stdin.readline
N, M=map(int, input().split())      # 세로, 가로
matrix=list()
dx=[-1, 1, 0, 0]    # 상하좌우
dy=[0, 0, -1, 1]

for n in range(N) :
    tmp=list(input().rstrip())
    if "R" in tmp :
        rx, ry=len(matrix), tmp.index("R")
    if "B" in tmp :
        bx, by=len(matrix), tmp.index("B")
    matrix.append(tmp)

def move(x, y, board, i) :
    a, b=x, y
    while True :
        nx, ny=a+dx[i], b+dy[i]
        if board[nx][ny] == 'O' :
            board[x][y]='.'
            return True, (nx, ny), board
        elif board[nx][ny] == '.' :
            a=nx
            b=ny
        else :
            board[a][b]=board[x][y]
            if x != a or y != b :
                board[x][y]='.'
            return False, (a, b), board


que=deque()
for i in range(4) :
    copied_matrix=copy.deepcopy(matrix)
    que.append([1, i, (rx, ry), (bx, by), copied_matrix])

while que :
    cnt, pos, red_now, blue_now, now_matrix=que.popleft()
    rx, ry=red_now
    bx, by=blue_now

    if cnt > 10 :
        break

    if pos == 0 :     # 상
        if rx > bx :
            b_flag, blue_pos, new_matrix=move(bx, by, now_matrix, pos)
            r_flag, red_pos, new_matrix=move(rx, ry, now_matrix, pos)
        else :
            r_flag, red_pos, new_matrix = move(rx, ry, now_matrix, pos)
            b_flag, blue_pos, new_matrix = move(bx, by, now_matrix, pos)
    elif pos == 1 :   # 하
        if rx > bx :
            r_flag, red_pos, new_matrix = move(rx, ry, now_matrix, pos)
            b_flag, blue_pos, new_matrix=move(bx, by, now_matrix, pos)
        else :
            b_flag, blue_pos, new_matrix = move(bx, by, now_matrix, pos)
            r_flag, red_pos, new_matrix = move(rx, ry, now_matrix, pos)
    elif pos == 2 :   # 좌
        if ry > by :
            b_flag, blue_pos, new_matrix = move(bx, by, now_matrix, pos)
            r_flag, red_pos, new_matrix = move(rx, ry, now_matrix, pos)
        else :
            r_flag, red_pos, new_matrix = move(rx, ry, now_matrix, pos)
            b_flag, blue_pos, new_matrix = move(bx, by, now_matrix, pos)
    elif pos == 3 :   # 우
        if ry > by :
            r_flag, red_pos, new_matrix = move(rx, ry, now_matrix, pos)
            b_flag, blue_pos, new_matrix = move(bx, by, now_matrix, pos)
        else :
            b_flag, blue_pos, new_matrix = move(bx, by, now_matrix, pos)
            r_flag, red_pos, new_matrix = move(rx, ry, now_matrix, pos)

    if not r_flag and not b_flag :
        if red_pos == red_now and blue_pos == blue_now : continue
        for i in range(4) :
            copied_matrix=copy.deepcopy(new_matrix)
            que.append([cnt+1, i, red_pos, blue_pos, copied_matrix])
    elif r_flag and not b_flag :
        print(cnt)
        sys.exit()

print(-1)

다른 사람의 풀이를 참고해서 작성했다.

빨간 구슬만 구멍에 넣었을 때 sys.exit()로 종료했다.

한 위치에서 4가지 방향을 다 고려해야 함

깊은 복사를 해야한다는 점을 주의하자.

 

# 실패
import sys, copy
from collections import deque

input=sys.stdin.readline
N, M=map(int, input().split())       # 세로, 가로
board=[]
for n in range(N) :
    row=list(input())
    if "R" in row :
        R_idx=(n, row.index("R"))
    if "B" in row :
        B_idx=(n, row.index("B"))
    board.append(row)

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

def move(x, y, d, new_board) :
    flag=False
    while True :
        nx=x+dx[d]
        ny=y+dy[d]
        if 0 < nx < N - 1 and 0 < ny < M - 1:
            if new_board[nx][ny] == "0" :
                flag=True
            if new_board[nx][ny] == "." :
                new_board[nx][ny] = 1
            else :
                break
        else :
            break
    return nx, ny, new_board, flag


def bfs() :
    ans=0       # 구슬을 굴리는 횟수
    que=deque([[R_idx, B_idx]])


    while que :
        r,b=que.popleft()

        if ans > 10 :
            return -1

        for i in range(4) :
            new_board=copy.deepcopy(board)
            if i == 0 :     # 상
                if r[0] < b[0] :
                    result_r=move(r[0], r[1], i, new_board)
                    result_b=move(b[0], b[1], i, new_board)
                else :
                    result_b = move(b[0], b[1], i, new_board)
                    result_r = move(r[0], r[1], i, new_board)

            elif i == 1 :   # 하
                if r[0] > b[0] :
                    result_r=move(r[0], r[1], i, new_board)
                    result_b=move(b[0], b[1], i, new_board)
                else :
                    result_b = move(b[0], b[1], i, new_board)
                    result_r = move(r[0], r[1], i, new_board)


            elif i == 2 :   # 우
                if r[1] > b[1] :
                    result_r=move(r[0], r[1], i, new_board)
                    result_b=move(b[0], b[1], i, new_board)
                else :
                    result_b = move(b[0], b[1], i, new_board)
                    result_r = move(r[0], r[1], i, new_board)


            elif i == 3 :   # 좌
                if r[1] < b[1] :
                    result_r=move(r[0], r[1], new_board)
                    result_b=move(b[0], b[1], new_board)
                else :
                    result_b = move(b[0], b[1], i, new_board)
                    result_r = move(r[0], r[1], i, new_board)

            if board[nx][ny] == "O" :
                return ans

            if board[nx][ny] == "O" :
                return -1
            deque.append([result_r, result_b])

        ans+=1

print(bfs())

 

# 실패
import sys
from collections import deque

input=sys.stdin.readline
N, M=map(int, input().split())       # 세로, 가로
board=[]
for n in range(N) :
    row=list(input())
    if "R" in row :
        R_idx=(n, row.index("R"))
    if "B" in row :
        B_idx=(n, row.index("B"))
    board.append(row)

dx=[-1, 1, 0, 0]
dy=[0, 0, 1, -1]

def move(x, y, d, visit) :
    while True :
        nx=x+dx[d]
        ny=y+dy[d]
        if 0 < nx < N - 1 and 0 < ny < M - 1:
            if board[nx][ny] == "." and not visit[nx][ny]:
                visit[nx][ny] = 1
        else :          # ???
            return nx, ny
    return nx, ny


def bfs() :
    ans=0       # 구슬을 굴리는 횟수
    que=deque([[R_idx, B_idx]])
    visit_r=[[0]*M for _ in range(N)]
    visit_b=[[0]*M for _ in range(N)]

    while que :
        r,b=que.popleft()
        if ans > 10 :
            return -1
        for i in range(4) :
            nx=r[0]+dx[i]
            ny=r[1]+dy[i]
            nx1=b[0]+dx[i]
            ny1=b[0]+dy[i]
            result_r=move(nx, ny, i, visit_r)
            if board[nx][ny] == "O" :
                return ans
            result_b=move(nx1, ny1, i, visit_b)
            if board[nx][ny] == "O" :
                return -1
            deque.append([result_r, result_b])

        ans+=1

print(bfs())

BFS

move 함수는 구슬이 한 방향으로 굴러가게 한다.

같은 행 또는 같은 열에 있을 때 어떤 구슬이 먼저 굴러가야 하는지를 고려 안 했다.

빨간 구슬과 파란 구슬이 제대로 굴러갈 수 있을 때 board에 반영되어야 한다.

그럴려면 move 함수에서 board를 깊은 복사한 2차원 리스트를 써야한다.

 

 

🍟 다른 사람 풀이

# https://donghak-dev.tistory.com/173?category=904697
from collections import deque
import copy

dx = [0,0,-1,1]
dy = [1,-1,0,0]

def move(d, arr, board):
    now_x, now_y = arr

    while True:
        nx, ny = now_x + dx[d], now_y + dy[d]

        if board[nx][ny] == ".":
            now_x, now_y = nx, ny

        elif board[nx][ny] == "O":
            board[arr[0]][arr[1]] = '.'     # 원래 구슬이 있던 위치는 빈 칸으로 바꾸기
            return now_x, now_y, True, board

        else:       # 더이상 못 굴러간다
            board[now_x][now_y] = board[arr[0]][arr[1]]     # 현재 좌표에 구슬두기
            if now_x != arr[0] or now_y != arr[1]:
                board[arr[0]][arr[1]] = '.'           # 구슬이 있었던 위치는 빈 칸으로 바꾸기
            return now_x, now_y, False, board


def solution():
    global answer

    Q = deque()
    for i in range(4):      # 네 방향 모두 생각하기
        new_board = copy.deepcopy(board)
        # [방향, 굴린 횟수, 빨간 구슬 위치, 파란 구슬 위치, 보드]
        Q.append([i, 1, red_ball, blue_ball, new_board])    

    while Q:

        direct, time, red_ball_now, blue_ball_now, now_board = Q.popleft()


        if time >= 11:
            return
        
        # 방향에 따라 먼저 굴러갈 구슬 고려하기
        if direct == 0:		# 우
            if red_ball_now[1] > blue_ball_now[1]:
                red_nx, red_ny, red_flag,new_board = move(direct, red_ball_now,now_board)
                blue_nx, blue_ny, blue_flag,new_board = move(direct, blue_ball_now,now_board)
            else:
                blue_nx, blue_ny, blue_flag,new_board = move(direct, blue_ball_now,now_board)
                red_nx, red_ny, red_flag,new_board = move(direct, red_ball_now,now_board)
        elif direct == 1:	# 좌
            if red_ball_now[1] < blue_ball_now[1]:
                red_nx, red_ny, red_flag,new_board = move(direct, red_ball_now,now_board)
                blue_nx, blue_ny, blue_flag,new_board = move(direct, blue_ball_now,now_board)
            else:
                blue_nx, blue_ny, blue_flag,new_board = move(direct, blue_ball_now,now_board)
                red_nx, red_ny, red_flag,new_board = move(direct, red_ball_now,now_board)
        elif direct == 2:	# 상
            if red_ball_now[0] < blue_ball_now[0]:
                red_nx, red_ny, red_flag,new_board = move(direct, red_ball_now,now_board)
                blue_nx, blue_ny, blue_flag,new_board = move(direct, blue_ball_now,now_board)
            else:
                blue_nx, blue_ny, blue_flag, new_board = move(direct, blue_ball_now,now_board)
                red_nx, red_ny, red_flag, new_board = move(direct, red_ball_now,now_board)
        else:		# 하
            if red_ball_now[0] > blue_ball_now[0]:
                red_nx, red_ny, red_flag, new_board = move(direct, red_ball_now,now_board)
                blue_nx, blue_ny, blue_flag, new_board = move(direct, blue_ball_now,now_board)
            else:
                blue_nx, blue_ny, blue_flag, new_board = move(direct, blue_ball_now,now_board)
                red_nx, red_ny, red_flag, new_board = move(direct, red_ball_now,now_board)


        if (blue_flag is False) and (red_flag is False):    # 두 구슬 다 아직 O에 못 들어감
            # 두 구슬 중 하나라도 현재 좌표와 move 메소드 실행 후 좌표가 다르면
            if [red_nx, red_ny] != red_ball_now or [blue_nx, blue_ny] != blue_ball_now:
                for i in range(4):      # 4가지 방향 다 고려
                    next_board = copy.deepcopy(new_board)
                    Q.append([i, time+1, [red_nx, red_ny], [blue_nx,blue_ny], next_board])

        elif (red_flag is True) and (blue_flag is False):   # 빨간 구슬만 구멍에 들어감
            answer = time
            return


N, M = map(int, input().split())
board = []

red_ball = [0,0]
blue_ball = [0,0]

for col in range(N):
    S = list(input())

    for i in range(len(S)):
        if S[i] == "R":
            red_ball = [col,i]      # 빨간 구슬 위치
        elif S[i] == "B":
            blue_ball = [col,i]     # 파란 구슬 위치
    board.append(S)

answer = -1
solution()

print(answer)

BFS, deque

pypy3로 제출해야 통과

'좌/우, 상/하로 구슬을 굴릴 때 먼저 굴러가야 하는 구슬부터 move 함수를 호출한다.

내가 구현하면서 생각 못했던 부분이다.

예제 7번 왼쪽으로 1번 굴리면 된다고 생각했었는데 -1이 답이라고 해서 이해가 안갔다.

같은 방향으로 굴렸을 때, 빨간 구슬이 먼저 O에 들어가면 성공이라고 생각했었다.

O를 만나면 원래 구슬 위치를 .으로 바꾸고 O는 그대로 둔다.

대신 red_flag / blue_flag를 사용해서 O에 들어갔다는 것을 나타내고, 빨간구슬/파란구슬을 담아 메소드를 또 호출

이렇게 하면 동시에 빨간 구슬, 파란 구슬이 들어간 것도 따진다.

O에 두 개가 들어갈 수 있다는 소리다.