Node.js) 백준 1941번: 소문난 칠공주

 

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

1941번: 소문난 칠공주

 

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 input = require('fs')
        .readFileSync('./dev/stdin')
        .toString()
        .trim()
        .split('\n')
        .map((v) => v.trim().split(''));

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

let answer = 0;
let board = Array.from(Array(5), () => Array(5));
for (let i = 0; i < 5; i++) {
        for (let j = 0; j < 5; j++) {
                board[i][j] = `${i}${j}`;
        }
}

const girls = board.flat();
for (let a = 0; a < girls.length; a++) {
        for (let b = a + 1; b < girls.length; b++) {
                for (let c = b + 1; c < girls.length; c++) {
                        for (let d = c + 1; d < girls.length; d++) {
                                for (let e = d + 1; e < girls.length; e++) {
                                        for (let f = e + 1; f < girls.length; f++) {
                                                for (let g = f + 1; g < girls.length; g++) {
                                                        let seven = [a, b, c, d, e, f, g].map((v) => girls[v]);
                                                        const isPossible =
                                                                seven
                                                                        .map((v) => input[+v[0]][+v[1]])
                                                                        .filter((v) => v == 'S').length >= 4;
                                                        if (!isPossible) continue;
                                                        const q = new Queue();
                                                        const last = seven.pop();
                                                        q.push([+last[0], +last[1]]);
                                                        while (q.length > 0) {
                                                                const [x, y] = q.pop();
                                                                for (let k = 0; k < 4; k++) {
                                                                        const nx = x + dx[k];
                                                                        const ny = y + dy[k];
                                                                        const next = `${nx}${ny}`;
                                                                        if (seven.includes(next)) {
                                                                                seven = seven.filter((v) => v != next);
                                                                                q.push([nx, ny]);
                                                                        }
                                                                }
                                                        }
                                                        if (seven.length == 0) {
                                                                answer++;
                                                        }
                                                }
                                        }
                                }
                        }
                }
        }
}

console.log(answer);