[골드2] 13460번 : 구슬 탈출2

hyunnn·2021년 4월 15일
0

코딩테스트 준비

목록 보기
82/83

🛠 문제

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


👩🏻‍💻 해결 방법

우선 빨간 구슬과 파란 구슬의 위치 저장을 위한 4차원 리스트 visit을 만들어주었다
구슬의 현재 위치에서부터 bfs를 적용해주기 위해 for문을 통해 현재 위치를 찾고, q에 넣어주었다
q에서 꺼낸 depth 값이 10 이상이면 break를 해주고, 그렇지 않으면 move 함수를 통해 한쪽 방향으로 기울였을 때 구슬의 위치를 구해주었다
파란 구슬이 'O'위치가 아니면서 빨간 구슬이 'O'위치일 때 depth를 출력해주었다
만약 두 구슬의 위치가 겹쳤을 경우, 더 많이 이동한 구슬을 한 칸 뒤로 이동시켜주는 과정이 필요했다
빨간 구슬의 위치가 'O'이 아닐 경우, 방문 처리를 해주고 q에 depth+1 값을 넣어 bfs를 계속 진행해주었다

소스 코드

from collections import deque
n, m = map(int, input().split())
board = [list(input()) for _ in range(n)]
visit = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]

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

q = deque()

def init():
    rx, ry, bx, by = 0, 0, 0, 0
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                rx, ry = i, j
            elif board[i][j] == 'B':
                bx, by = i, j
    q.append((rx, ry, bx, by, 1))
    visit[rx][ry][bx][by] = True

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 solve():
    init()
    while q:
        rx, ry, bx, by, depth = q.popleft()

        if depth > 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':
                if board[nrx][nry] == 'O':
                    print(depth)
                    return

                if nrx == nbx and nry == nby:
                    if rcnt > bcnt:
                        nrx -= dx[i]
                        nry -= dy[i]
                    else:
                        nbx -= dx[i]
                        nby -= dy[i]

                if not visit[nrx][nry][nbx][nby]:
                    visit[nrx][nry][nbx][nby] = True
                    q.append((nrx, nry, nbx, nby, depth+1))
    print(-1)

solve()

관심 있을 만한 포스트

0개의 댓글