[BOJ] 3055 - 탈출 (Python, JavaScript)

 

 

아이디어

 

BFS로 고슴도치가 비버의 굴로 이동하는 최소 시간을 구한다.

 

 

풀이 #1 (Python)

 

import sys

input = sys.stdin.readline

def solution():
    R, C = map(int, input().split())
    board = [[*input().rstrip()] for _ in range(R)]
    delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    queue = []
    for r in range(R):
        for c in range(C):
            if board[r][c] == 'S':
                board[r][c] = 1
                queue.append((r, c, 1))
            elif board[r][c] == '*':
                queue.append((r, c, 0))
    queue.sort(key=lambda x: x[2])
    while queue:
        r, c, s = queue.pop(0)
        for dr, dc in delta:
            nr, nc = r+dr, c+dc
            if R > nr >= 0 and C > nc >= 0:
                if s:
                    if board[nr][nc] == '.':
                        board[nr][nc] = board[r][c]+1
                        queue.append((nr, nc, s))
                    elif board[nr][nc] == 'D':
                        print(board[r][c])
                        return
                elif board[nr][nc] == '.':
                    board[nr][nc] = '*'
                    queue.append((nr, nc, s))
    print('KAKTUS')

solution()

 

 

 

풀이 #2 (JavaScript)

 

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

function solution() {
    const [R, C] = input[0].split(' ').map(Number);
    let board = [];
    for (let i=1; i<=R; i++) {
        board.push(input[i].split(''));
    }
    const delta = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    let queue = [];
    for (let r=0; r<R; r++) {
        for (let c=0; c<C; c++) {
            if (board[r][c] === 'S') {
                board[r][c] = 1;
                queue.push([r, c, 1]);
            }
            else if (board[r][c] === '*') queue.push([r, c, 0]);
        }
    }
    queue.sort((a, b) => a[2]-b[2]);
    while (queue.length) {
        const [r, c, s] = queue.shift();
        for (const [dr, dc] of delta) {
            const [nr, nc] = [r+dr, c+dc];
            if (nr < R && nr >= 0 && nc < C && nc >= 0) {
                if (s) {
                    if (board[nr][nc] === '.') {
                        board[nr][nc] = board[r][c]+1;
                        queue.push([nr, nc, s]);
                    }
                    else if (board[nr][nc] === 'D') {
                        console.log(board[r][c]);
                        return;
                    }
                }
                else if (board[nr][nc] === '.') {
                    board[nr][nc] = '*';
                    queue.push([nr, nc, s]);
                }
            }
        }
    }
    console.log('KAKTUS');
}

solution();