[백준] 12886번 돌 그룹 Javascript(NodeJs)

문제 링크

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

알고리즘: BFS

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

풀이

이 문제의 핵심은 3개 그룹의 총합은 고정이라는 것이다. 즉 visited 처리를 2차원 배열로 처리할 수 있다. 왜냐하면 두 개가 결정되면 나머지 하나는 무조건 고정값을 가지기 때문이다. 이것만 알고 풀면 쉽게 BFS로 풀이가 가능하다.

소스코드

class Queue {
    constructor() {
        this.storage = {};
        this.front = 0;
        this.rear = -1
    }
    
    size() {
        if(this.front > this.rear) {
            return 0;
        } else {
            return this.rear - this.front + 1;
        }
    }
    
    push(value) {
        this.rear += 1;
        this.storage[this.rear] = value;
    }
    
    pop_left() {
        let value = this.storage[this.front];
        if(this.size()) {
            this.front += 1;
        }
        return value;
    }
}
const fs = require('fs');
let [A,B,C] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);
let visited = Array.from(Array(1501), () => Array(1501).fill(0));
console.log(BFS());

function BFS() {
    let que = new Queue();
    que.push([A,B,C]);
    let sn = [[0,1,2], [0,2,1], [1,2,0]]; //select number
    while(que.size()) {
        let rockGup = que.pop_left();
        if(rockGup[0]===rockGup[1] && rockGup[1]===rockGup[2]) {
            return 1;
        }
        for(let i=0; i<sn.length; i++) {
            let [n1,n2,left] = sn[i];
            if(rockGup[n1] !== rockGup[n2]) {
                let a,b;
                let c = rockGup[left];
                if(rockGup[n1] > rockGup[n2]) {
                    //rockGup[n1]이 더 큰 경우
                    a = rockGup[n1] - rockGup[n2];
                    b = rockGup[n2] * 2;
                } else {
                    //rockGup[n2]가 더 큰 경우
                    a = rockGup[n2] - rockGup[n1];
                    b = rockGup[n1] * 2;
                }
                if(visited[a][b]===0) {
                     visited[a][b] = 1;
                     visited[b][a] = 1;
                     que.push([a,b,c]);
                }
            }
        }
    }
    return 0;
}