[BOJ] 13460 - 구슬 탈출 2 (Python, JavaScript)

 

 

아이디어

 

13459번 구슬 탈출 문제와 출력만 다른 문제로, BFS로 구슬을 이동하며 구멍에 빨간 구슬만 넣을 수 있는지 확인한다.

 

 

풀이 #1 (Python)

 

import sys

input = sys.stdin.readline

delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solution():
    N, M = map(int, input().split())
    board = [input().rstrip() for _ in range(N)]
    rr = rc = br = bc = 0
    for r in range(N):
        for c in range(M):
            if board[r][c] == 'R':
                rr, rc = r, c
            elif board[r][c] == 'B':
                br, bc = r, c
    visited = [[[[-1]*M for _ in range(N)] for _ in range(M)] for _ in range(N)]
    visited[rr][rc][br][bc] = 0
    queue = [(rr, rc, br, bc)]
    while queue:
        _queue = []
        while queue:
            rr, rc, br, bc = queue.pop()
            for dr, dc in delta:
                nrr, nrc, nbr, nbc = rr, rc, br, bc
                rd = bd = 0
                while board[nrr+dr][nrc+dc] != '#':
                    if board[nrr+dr][nrc+dc] == 'O':
                        nrr = nrc = -1
                        break
                    nrr += dr
                    nrc += dc
                    rd += 1
                while board[nbr+dr][nbc+dc] != '#':
                    if board[nbr+dr][nbc+dc] == 'O':
                        nbr = nbc = -1
                        break
                    nbr += dr
                    nbc += dc
                    bd += 1
                if nbr == -1:
                    continue
                if nrr == -1:
                    print(visited[rr][rc][br][bc]+1)
                    return
                if nrr != rr or nrc != rc or nbr != br or nbc != bc:
                    if nrr == nbr and nrc == nbc:
                        if rd < bd:
                            nbr -= dr
                            nbc -= dc
                        else:
                            nrr -= dr
                            nrc -= dc
                    if visited[nrr][nrc][nbr][nbc] < 0:
                        visited[nrr][nrc][nbr][nbc] = visited[rr][rc][br][bc]+1
                        if visited[nrr][nrc][nbr][nbc] < 10:
                            _queue.append((nrr, nrc, nbr, nbc))
        queue = _queue
    print(-1)

solution()

 

 

 

풀이 #2 (JavaScript)

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function solution() {
    const delta = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    const [N, M] = input[0].split(' ').map(Number);
    let board = [];
    for (let i=1; i<=N; i++) {
        board.push(input[i]);
    }
    let rr = rc = br = bc = 0;
    for (let r=0; r<N; r++) {
        for (let c=0; c<M; c++) {
            if (board[r][c] === 'R') [rr, rc] = [r, c];
            if (board[r][c] === 'B') [br, bc] = [r, c];
        }
    }
    let visited = Array.from(Array(N), () => Array.from(Array(M), () => Array.from(Array(N), () => Array(M).fill(-1))));
    visited[rr][rc][br][bc] = 0;
    queue = [[rr, rc, br, bc]];
    while (queue.length) {
        let _queue = [];
        while (queue.length) {
            const [rr, rc, br, bc] = queue.pop();
            for (const [dr, dc] of delta) {
                let [nrr, nrc, nbr, nbc] = [rr, rc, br, bc];
                let rd = bd = 0;
                while (board[nrr+dr][nrc+dc] !== '#') {
                    if (board[nrr+dr][nrc+dc] === 'O') {
                        nrr = nrc = -1;
                        break;
                    }
                    nrr += dr;
                    nrc += dc;
                    rd += 1;
                }
                while (board[nbr+dr][nbc+dc] !== '#') {
                    if (board[nbr+dr][nbc+dc] === 'O') {
                        nbr = nbc = -1;
                        break;
                    }
                    nbr += dr;
                    nbc += dc;
                    bd += 1;
                }
                if (nbr === -1) continue;
                if (nrr === -1) {
                    console.log(visited[rr][rc][br][bc]+1);
                    return;
                }
                if (nrr !== rr || nrc !== rc || nbr !== br || nbc !== bc) {
                    if (nrr === nbr && nrc === nbc) {
                        if (rd < bd) {
                            nbr -= dr;
                            nbc -= dc;
                        }
                        else {
                            nrr -= dr;
                            nrc -= dc;
                        }
                    }
                    if (visited[nrr][nrc][nbr][nbc] < 0) {
                        visited[nrr][nrc][nbr][nbc] = visited[rr][rc][br][bc]+1;
                        if (visited[nrr][nrc][nbr][nbc] < 10) _queue.push([nrr, nrc, nbr, nbc]);
                    }
                }
            }
        }
        queue = _queue;
    }
    console.log(-1);
}

solution();