Node.js) 백준:17142번: 연구소 3

 

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

17142번: 연구소 3

 

class Node {

        constructor(item) {

                this.item = item;

                this.next = null;

        }

}

class Queue {

        constructor() {

                this.head = null;

                this.tail = null;

                this.length = 0;

        }

        push(item) {

                const node = new Node(item);

                if (this.head == null) {

                        this.head = node;

                } else {

                        this.tail.next = node;

                }

                this.tail = node;

                this.length += 1;

        }

        pop() {

                const popItem = this.head;

                this.head = this.head.next;

                this.length -= 1;

                return popItem.item;

        }

}

const fs = require('fs');

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

const [N, M] = input.shift().split(' ').map(Number);

let Lab = input.map((v) => v.split(' ').map(Number));

let answer = Infinity;

const virus = [];

const virusLab = [];

for (let i = 0; i < N; i++) {

        for (let j = 0; j < N; j++) {

                if (Lab[i][j] == 2) {

                        virus.push([i, j]);

                        Lab[i][j] = '*';

                } else if (Lab[i][j] == 1) {

                        Lab[i][j] = '-';

                } else if (Lab[i][j] == 0) {

                        Lab[i][j] = Infinity;

                }

        }

}

function bfs(x, y) {

        const dr = [0, 0, 1, -1];

        const dc = [1, -1, 0, 0];

        let tempLab = Lab.map((v) => [...v]);

        const q = new Queue();

        q.push([x, y, 0]);

        tempLab[x][y] = 0;

        while (q.length > 0) {

                const [r, c, t] = q.pop();

        }

        virusLab.push(tempLab);

}

virus.forEach(([x, y]) => {

        bfs(x, y);

});

const V = virus.length;

// V Combination M

for (let i = 0; i <= (1 << V) - 1; i++) {

        let j = i;

        const selected = [];

        let index = 0;

        while (j > 0) {

                if ((j & 1) == 1) {

                        selected.push(index);

                }

                j >>= 1;

                index++;

        }

        if (selected.length == M) {

                const dx = [0, 0, 1, -1];

                const dy = [1, -1, 0, 0];

                const q = new Queue();

                let injectedLab = Lab.map((v) => [...v]);

                selected.forEach((v) => {

                        const [x, y] = virus[v];

                        q.push([x, y, 0]);

                        injectedLab[x][y] = 0;

                });

                while (q.length > 0) {

                        const [x, y, t] = q.pop();

                        for (let i = 0; i < 4; i++) {

                                const nx = x + dx[i];

                                const ny = y + dy[i];

                                if (

                                        nx >= 0 &&

                                        nx < N &&

                                        ny >= 0 &&

                                        ny < N &&

                                        injectedLab[nx][ny] != '-' &&

                                        injectedLab[nx][ny] > t + 1

                                ) {

                                        injectedLab[nx][ny] = t + 1;

                                        q.push([nx, ny, t + 1]);

                                } else if (nx >= 0 && nx < N && ny >= 0 && ny < N && injectedLab[nx][ny] == '*') {

                                        injectedLab[nx][ny] = t + 1;

                                        q.push([nx, ny, t + 1]);

                                }

                        }

                }

                virus.filter((v, i) => {

                        if (!selected.includes[i]) {

                                return v;

                        }

                }).forEach(([x, y]) => {

                        injectedLab[x][y] = '*';

                });

                let time = 0;

                for (let i = 0; i < N; i++) {

                        for (let j = 0; j < N; j++) {

                                if (injectedLab[i][j] == '-' || injectedLab[i][j] == '*') continue;

                                time = time > injectedLab[i][j] ? time : injectedLab[i][j];

                        }

                }

                answer = answer > time ? time : answer;

        }

}

console.log(answer === Infinity ? -1 : answer);