[BaekJoon] 13460 구슬탈출 2

🔦 문제 링크

✍️ 풀이

---

• 최소 이동을 구해 빠져나오면 되므로 BFS로 구한다.
• 빨간구슬과 파란구슬의 동시에 움직이기에 4차원배열을 통해 방문여부를 검사한다. (블로그를 참고)

중요 포인트

• #을 만났을 땐 dx, dy를 더하고 검사하지만 O를 만났을 땐 더해기 전에 검사를 한다. (#과 O를 구분할 수 있다)
• 만약 두 구슬 위치가 같다면 더 많이 움직인 구슬을 한 칸이전으로 돌려줘야한다.

구슬의 다음 위치가 #이라면 멈춘다. 구슬의 현재 위치가 구멍이라면, 현재 구슬의 색이 무엇인지 판별한다.
빨간 구슬이라면 1을 출력하고 종료한다.

🛠 코드

---

import sys
from collections import deque
r, c = map(int, input().split())
arr = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
check = [[[[False]*c for _ in range(r)] for _ in range(c)] for _ in range(r)]
blue = red = []

dx = (0,0,-1,1)
dy = (-1,1,0,0)


def init():
    global blue, red
    for i in range(1, r - 1):
        for j in range(1, c - 1):
            if arr[i][j] == 'B':
                blue = [i, j]
            elif arr[i][j] == 'R':
                red = [i, j]


def move(val, i):
    x, y = val[0], val[1]
    n = 0
    while arr[x+dx[i]][y+dy[i]] != '#' and arr[x][y] != 'O':
        x += dx[i]
        y += dy[i]
        n += 1
    return x, y, n


def bfs():
    q = deque()
    cnt = 0
    check[blue[0]][blue[1]][red[0]][red[1]] = True
    q.append((blue, red, cnt))
    while q:
        bl, re, cn = q.popleft()
        if cn >= 10:
            break
        for i in range(4):
            bx, by, bn = move(bl, i)
            rx, ry, rn = move(re, i)
            if arr[bx][by] == 'O':
                continue
            elif arr[rx][ry] == 'O':
                print(cn+1)
                return
            if rx == bx and ry == by:  # 위치가 같다면 한 칸이전으로 이동
                if bn > rn:
                    bx -= dx[i]
                    by -= dy[i]
                else:
                    rx -= dx[i]
                    ry -= dy[i]
            if not check[bx][by][rx][ry]:
                check[bx][by][rx][ry] = True
                tmp = ((bx, by), (rx, ry), cn+1)
                q.append(tmp)
    print(-1)


init()
bfs()

📝 정리

---

• 4차원 배열을 선언해 방문여부 검사

🎈 참고

---

rebas님 블로그