구슬 탈출2 문제 보러가기

BFS 알고리즘이란? 너비 우선 탐색으로 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 알고리즘이다.

• 재귀적으로 동작하지 않는다
• 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다
• 큐(Queue)를 사용한다.
• 선입선출(FIFO)
• 시간복잡도
  • 인접 리스트 : $O(N+E)$
  • 인접 행렬 : $O(N^{2})$

---

주어진 문제에서 내가 얻을 수 있는 단서? 는 무엇이 있었는지 핵심 포인트를 초록색으로 표시를 해보았다.
이해하고 분석하는데 초점을 맞췄다.
(주어진 문제를 어떻게 코드로 표현할 수 있는지에 초점을 맞췄다)
어떻게 풀어야 하는지 설계까지만 하고 구현은 완벽히 하지 못했다..

문제

---

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

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

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

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

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

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

---

핵심 포인트 요약

• 빨간 구슬을 구멍을 통해 빼내는 게임이다.
  👉 빨간 구슬이 구멍에 도착하면 성공

• 보드의 세로 크기는 N, 가로 크기는 M
  👉 2차원 행렬 형태

• 파란 구슬이 구멍에 들어가면 안 된다.
  👉 파란 구슬이 구멍에 도착하면 실패

• 네 가지 동작 가능(기울이기), 각각의 동작에서 공(파란,빨간)은 동시에 움직인다.
  👉 기울인다는 동작은 한번 기울이게되면 벽이 닿을때까지 그 방향으로 계속 이동한다는 의미이며, 이러한 동작을 1회 시행할때 파란공, 빨간공 각각 적용시켜줘야 한다는 점이다.

  보통 어떠한 객체의 동작을 나타날때 함수를 이용하면 좀 더 직관적인 코드를 작성할 수 있을거라 생각된다.

• 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.
  👉 1회 시행할때 파란공과 빨간공을 둘다 움직여야 하는데 만약 같은 행 또는 같은 열에 있을 경우 한 쪽방향으로 기울이게 되면 서로 겹치게 된다. 이를 어떻게 처리해야하는지 생각을 해야한다.

• 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램
  👉 최종적으로 우리의 목표가 되겠으며 최소 몇 번 만에라는 것은 최소 몇 번 보드판을 기울여서 빨간 구슬을 구멍에 도착하게 하면 되는지 알아내는 것이다.

---

코드

from collections import deque
import sys
input = sys.stdin.readline

# 보드의 크기 (세로, 가로) / 보드판 초기화
N, M = map(int, input().split())
board = [list(input().strip()) for _ in range(N)]

# 빨간색공의 좌표x,y 파란색공의 좌표x,y를 4차원 배열로 표현
visited = [[[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N)]

# 네 가지 기울이기 동작 (오른쪽, 아래쪽, 왼쪽, 위쪽) 
dydx = [(0,1), (1,0), (-1,0), (0,-1)]

# 어떤 좌표에서 동작을 시작할지 기록하는 용도라고 생각함
que = deque()

# 구슬 동작을 시작하기 위한 준비단계
def prep():
    # (빨간공의 x좌표, 빨간공의 y좌표, 파란공의 x좌표, 파란공의 y좌표)
    red_x, red_y, blue_x, blue_y = [0]*4	# (0, 0, 0, 0)
    
    for y in range(N):
        for x in range(M):
            if board[y][x] == 'R':		# board판에 있는 처음 빨간 구슬 좌표 초기화
                red_y, red_x = y, x
            elif board[y][x] == 'B':	# board판에 있는 처음 파란 구슬 좌표 초기화
                blue_y, blue_x = y, x
                    
    que.append((red_y, red_x, blue_y, blue_x, 1))	# 처음 시작할 지점
    visited[red_y][red_x][blue_y][blue_x] = True	
    # 처음 시작한 지점에 대해서 방문 체크를 해줌(나중에 중복수행을 하지 않기 위함)


# 구슬이 움직이는 동작 표현
def move(y, x, dy, dx):
    count = 0	# 이동한 칸 수
    # 이동한 칸 수를 알게되면 어느 구슬이 더 많이 움직인지 알 수 있음
        
    while board[y+dy][x+dx] != '#' and board[y][x] != 'O':
        # 다음에 이동할 좌표가 벽이 아니거나 현재 좌표가 구멍이 아닐 경우에
        y += dy
        x += dx
        # 현재 좌표를 한칸 전진하고
        count += 1
        # 한칸 전진했으므로 +1을 해준다
                
    return y, x, count

# 본격적으로 구슬을 이동시켜 구멍을 찾는 과정 (BFS 알고리즘 사용)
def solution():
    prep()	# 구슬 동작을 시작하기 위해 준비단계 함수 수행
        
    # 더이상 구슬이 움직이지 않을 때까지 반복(성공하거나 실패할때까지)
    while que:
        red_y, red_x, blue_y, blue_x, n = que.popleft()
            
        # 구슬이 움직이는 횟수는 10번 이하여야 함 (10번까지댐)
        if n > 10:
            break
            
        # 네 가지 기울이기 동작 시행
        for dy,dx in dydx:
            next_ry, next_rx, r_count = move(red_y, red_x, dy, dx)	# 빨간 구슬 이동
            next_by, next_bx, b_count = move(blue_y, blue_x, dy, dx) # 파란 구슬 이동
            # 만약 구멍을 만났다면 해당 구슬 좌표의 위치는 구멍에서 멈추게 되고
            # 구멍없이 벽을 만났다면 해당좌표는 벽 앞에서 멈추게 됨
                
            # 파란구슬이 구멍에 도착했다면 실패
            if board[next_by][next_bx] == 'O':
                continue
                
            # 빨간구슬이 구멍에 도착했다면 성공
            if board[next_ry][next_rx] == 'O':
                print(n);return
                
            # 빨간공과 파란공이 같은 위치에서 멈추면 (겹치게된다면)
            if next_ry == next_by and next_rx == next_bx:
                # 움직임이 많은 구슬이 다른 구슬보다 한칸 적어야함
                if r_count > b_count:
                    next_ry -= dy
                    next_rx -= dx
                else:
                    next_by -= dy
                    next_bx -= dx
                
            # 1회의 구슬 이동을 마치고 도달한 좌표값이 예전에 방문했던 적이 없다면 새로 큐에 추가
            if not visited[next_ry][next_rx][next_by][next_bx]:
                visited[next_ry][next_rx][next_by][next_bx] = True
                que.append((next_ry, next_rx, next_by, next_bx, n+1))
            
    print(-1)
            
solution()

---

좀 더 생각이 필요한 부분 (정확하진 않아서 참고만)

visited = [[[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N)]

👉 why? 방문체크하는 배열을 왜 4차원으로 표현했을까?

• 변수 4개에 대해서 경우의 수를 표현해주는 공간이라고 생각했다. 즉, 여기서는 빨간색 공의 x좌표와 y좌표 그리고 파란색 공의 x좌표와 y좌표 이렇게 4개의 변수에 대해서 모든 경우의 수를 한번에 표현해주는 방법이라고 생각한다.
• 예제 입력1을 예로 들면 5x5 행렬에서 visited 배열을 만들게 되면 5x5x5x5 크기로 전체 625가지의 경우의 수가 나온다. 이는 빨간색 공의 x,y좌표 그리고 파란색 공의 x,y좌표를 동시에 보드판에 놓을 수 있는 경우의 수가 625가지라고 생각한다.

def move(x, y, dx, dy):
	count = 0
    
    while board[y+dy][x+dx] != '#' and board[y][x] != 'O':
    	y += dy
        x += dx
        count += 1
        
    return x, y, count

👉 이동한 칸의 수를 저장하는 count의 변수의 필요성

• 결론부터 말하자면 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.를 처리하기 위한 변수 이다.
• 만약 두개의 구슬(빨간, 파란)이 같은 행이나 같은 열에 있다고 한다면 한쪽으로 기울였을때 두 구슬 모두 같은 방향으로 움직일 것이며, 두 구슬은 중간에 구멍을 만나지 않는다면 벽에 닿기 전에 겹쳐지게 된다.
  이동한 칸 수를 따로 저장하게되면 어느 구슬이 먼저 벽쪽에 도착하는지 알 수 있다. 바로 벽이랑 거리가 가까운 구슬이 벽쪽에 먼저 도달하게 될 것이고,
  두 구슬이 서로 겹치지 않으려면 벽이랑 거리가 상대적으로 멀리 있는 구슬(움직임이 가장 많은 구슬)이 다른 구슬보다 한칸 적어야한다.
• 따라서 빨간색공의 count와 파란색공의 count를 비교해서 더 많이 움직인 구슬을 이동한 방향에서 한칸 뒤로 후퇴 시키면 된다.

que.append((red_y, red_x, blue_y, blue_x, 1))

👉 처음 prep() 함수의 구슬 동작을 시작하기 위한 준비단계에서 que의 마지막 값인 몇번 구슬이 움직였는지(몇번 보드판을 기울였는지)를 1로 셋팅한 이유

• 이부분은 solution()의 함수 동작과정을 따라가다보면 쉽게 이해할 수 있을 것 같다. 대략적으로 설명하자면 n을 몇번 보드판을 기울였는지를 나타내는 변수라고 할때 n을 먼저 1증가시킨다음에 실제 보드판을 기울이는 동작이 수행된다고 생각하면 좋을 것 같다.

---

혹시나 설명이 잘못된 부분이 있으면 댓글 부탁드립니다.