[백준] 13460 - 구슬 탈출 2 [Python(파이썬)]

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀
문제 👉 13460번: 구슬 탈출 2

1. 문제

1. N*M 크기의 보드에서 기울이는 동작을 통해 파란 구슬은 냅두고 빨간 구슬만 구멍으로 뺀다.
2. '.'은 빈 칸, '#'은 벽, 'O'는 구멍, 'R'은 빨간 구슬, 'B'는 파란 구슬을 의미한다.
3. 기울이는 동작은 동,서,남,북 4방향이다.
4. 모든 보드의 가장자리에는 모두 벽('#')이 있다.
5. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
6. 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

2. 풀이

BFS 를 이용한 문제 풀이 (최소 거리 -> BFS -> 큐)

1. 초기 각 구슬과 구멍 및 장애물의 위치 배열에 저장
2. 구슬이 들렸던 위치를 배열에 저장
3. 각 구슬의 위치와 depth를 큐에 저장
4. BFS 함수 구현
   1. 종료 조건
      1. cnt == 10
   2. 탐색
      1. 4방향으로 각 구슬 이동
      2. 빨간공만 구멍일 때 종료
      3. 두 공이 같은 위치일 때 많이 움직인 걸 뒤로 이동
      4. 두 공의 위치가 이전에 들렸던 곳이 아니라면 기록하고 큐에 추가

3. 코드

from collections import deque

def solution():
    N, M = map(int, input().split())
    B = [list(input().strip()) for _ in range(N)]
    dx, dy = [-1,1,0,0] ,[0,0,-1,1]
    que = deque() # BFS : queue 활용
    # 구슬이 들렸던 위치 저장
    visited = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]

    def init(): # 초기 구슬의 좌표를 큐에 저장
        rx, ry, bx, by = 0, 0, 0, 0
        for i in range(N):
            for j in range(M):
                if B[i][j] == 'R':
                    rx, ry = i, j
                elif B[i][j] == 'B':
                    bx, by = i, j
        que.append((rx,ry,bx,by, 1)) # 구슬의 위치와 depth 저장
        visited[rx][ry][bx][by] = True # 구슬이 들렸던 위치 기록

    def move(x, y, dx, dy):
        cnt = 0 # 이동한 칸 수
        while B[x+dx][y+dy] != '#' and B[x][y] != 'O': # 다음이 벽이 아니고 현재가 구멍이 아닐 때 까지
            x += dx
            y += dy
            cnt += 1
        return x, y, cnt

    def bfs():
        init()
        while que:
            rx, ry, bx, by, cnt = que.popleft()
            if cnt > 10:
                return -1

            for i in range(4): # 4방향
                nrx, nry, nrc = move(rx, ry, dx[i], dy[i])
                nbx, nby, nbc = move(bx, by, dx[i], dy[i])
                if B[nbx][nby] != 'O':
                    if B[nrx][nry] == 'O':
                        return cnt # 빨간 구슬만 구멍일 때
                    if nrx == nbx and nry == nby: # 두 구슬의 위치가 같을 때 depth가 높은 걸 뒤로 이동
                        if nrc > nbc:     
                            nrx -= dx[i]
                            nry -= dy[i] 
                        else:
                            nbx -= dx[i]
                            nby -= dy[i]
                    if not visited[nrx][nry][nbx][nby]: # 구슬 위치 기록
                        visited[nrx][nry][nbx][nby] = True
                        que.append((nrx, nry, nbx, nby, cnt+1))
        return -1

    return bfs()

print(solution())

• 결과는 92 ms 나왔다.

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋