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

문제 설명

 

입출력 예제

 

---

풀이 코드

골드1 난이도인 만큼 이전 BFS문제보다 상당히 까다로웠다.

 

1. 먼저 빨강 공과 파란 공의 위치를 방문했는지 확인할 필요가 있다.

이 부분을 visited 리스트에 공들의 위치 값을 튜플로 넣어 방문 여부를 확인하였다.

 

2. 주어진 입력 값에서 빨강 공의 위치와 파란 공의 위치를 반환.

getPos()라는 메서드를 만들어 각 공의 위치를 반환하도록 하였다.

 

3. 각 공이 구멍전까지 도달하는데 걸리는 기울이기 횟수를 구한다.

move() 함수를 통해 이동하는 위치가 벽이아니고, 구멍에 들어가지 않을 동안 반복하여 각 공의 기울이기 횟수를 구하였다.

이 기울이기 횟수는 두 공의 위치가 겹쳤을 경우를 처리하기 위해 사용한다.

 

4. bfs를 통해 빨강 공이 구멍에 도달하면 result를 반환한다.

 

정답 코드

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

n, m = map(int, input().split()) # 행, 열

board = [list(input().rstrip()) for _ in range(n)]
visited = []

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

def getPos():
    rx, ry, bx, by = 0, 0, 0, 0
    for x in range(n):
        for y in range(m):
            if board[x][y] == "R":
                rx, ry = x, y
            if board[x][y] == "B":
                bx, by = x, y
    return rx, ry, bx, by


def move(x, y, dx, dy):
    cnt = 0
    # 이동하는 위치가 벽이아니고, 구멍에 들어가지 않을 동안 반복
    while board[x + dx][y + dy] != "#" and board[x][y] != "O":
        x += dx
        y += dy
        cnt +=1
    return x, y, cnt
    
def bfs():
    rx, ry, bx, by = getPos()

    q = deque()
    q.append((rx, ry, bx, by, 1))
    visited.append((rx, ry, bx, by))

    while q:
        rx, ry, bx, by, result = q.popleft()

        if result > 10:
            break

        for i in range(4):
            nrx, nry, rcnt = move(rx, ry, dx[i], dy[i])
            nbx, nby, bcnt = move(bx, by, dx[i], dy[i])

            # 파란 구슬이 구멍에 들어갈 경우
            if board[nbx][nby] == "O":
                continue

            # 빨간 구슬이 들어갈 경우 성공
            if board[nrx][nry] == "O":
                print(result)
                return

            # 둘이 겹쳐있을경우 더 많이 이동한녀석을 1칸 뒤로 보낸다.
            if nrx == nbx and nry == nby:
                if rcnt > bcnt:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]

            # 탐색하지 않은 방향 탐색
            if (nrx, nry, nbx, nby) not in visited:
                visited.append((nrx, nry, nbx, nby))
                q.append((nrx, nry, nbx, nby, result + 1))
    print(-1)

bfs()