[백준] 21608 상어 초등학교 (Javascript)

문제

BOJ21608_상어 초등학교

풀이

요구사항

학생의 번호와, 그 학생이 좋아하는 친구의 번호 4개가 순서대로 주어진다.
주어진 순서대로 조건에 맞게 학생들의 자리를 배치했을 때, 학생들의 총 만족도를 구하시오.
조건은 아래와 같다.

1. 인접한 네 방향에 좋아하는 학생이 가장 많은 좌표에 현재 학생을 배치한다.
2. 좌표가 여러개일 경우, 인접한 네 방향에 빈 칸이 가장 많은 좌표에 현재 학생을 배치한다.
3. 좌표가 여러개일 경우, y축이 가장 작은 좌표에 배치한다.
4. 좌표가 여러개일 경우, x축이 가장 작은 좌표에 배치한다.

만족도를 구하는 방법은 아래와 같다.

인접한 칸에 앉은 좋아하는 학생의 수	만족도
0	0
1	1
2	10
3	100
4	1000

해결방안

한 학생마다 N*N 배열을 순회한다.
배열을 순회하며 각 칸마다 인접한 칸(상,하,좌,우)을 확인한 뒤, 인접한 칸에 있는 좋아하는 학생의 수와 빈칸의 수를 구해서 [좋아하는 학생의 수, 빈 칸의 수, y좌표, x좌표] 꼴로 배열에 저장한다.

배열 순회를 모두 마쳤으면 저장해둔 배열을 좋아하는 학생의 수를 기준으로 내림차순, 빈 칸의 수를 기준으로 내림차순, y좌표를 기준으로 오름차순, x좌표를 기준으로 오름차순 정렬해준다.

그럼 문제에서 나온 조건에 부합하는 좌표가 [0]번 인덱스로 온다. 그럼 0번 인덱스에 있는 y좌표와 x좌표에 해당 학생을 배치한다.

이 과정을 반복해서 모든 학생을 자리에 배치했으면 다시 한번 N*N 배열을 순회하며 인접한 칸을 확인해서 좋아하는 학생의 수에따라 만족도를 누적해주면 답을 구할 수 있다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const arr = input.slice(1).map((e) => e.split(' ').map(Number));
const classRoom = Array.from({ length: N }, () => Array(N));
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

function bruteforce(favorite) {
    const pos = [];

    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            // 현재 자리가 비어있다면 인접한 방향 확인
            if (classRoom[i][j] === undefined) {
                const [favoriteCount, blankCount] = checkDirection(i, j, favorite);
                pos.push([favoriteCount, blankCount, i, j]);
            }
        }
    }

    pos.sort((a, b) => {
        if (a[0] !== b[0]) return b[0] - a[0];
        if (a[1] !== b[1]) return b[1] - a[1];
        if (a[2] !== b[2]) return a[2] - b[2];
        if (a[3] !== b[3]) return a[3] - b[3];
    });

    return pos[0];
}

function checkDirection(y, x, favorite) {
    let favoriteCount = 0;
    let blankCount = 0;

    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
            // 인접한 방향에 좋아하는 학생이 있다면
            if (favorite.some((e) => e === classRoom[ny][nx])) favoriteCount++;
            // 인접한 방향에 빈 칸이 있다면
            else if (classRoom[ny][nx] === undefined) blankCount++;
        }
    }
    return [favoriteCount, blankCount];
}

function checkSatisfiction(y, x) {
    let favoriteCount = 0;
    const row = arr.find((e) => e[0] === classRoom[y][x]);
    const favorite = row.slice(1);

    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
            // 인접한 방향에 좋아하는 학생이 있다면
            if (favorite.some((e) => e === classRoom[ny][nx])) favoriteCount++;
        }
    }
    return Math.floor(10 ** (favoriteCount - 1));
}

for (let row of arr) {
    const studentNum = row[0];
    const favorite = row.slice(1);
    const [_, __, y, x] = bruteforce(favorite);
    classRoom[y][x] = studentNum;
}

let answer = 0;
for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
        answer += checkSatisfiction(i, j);
    }
}

console.log(answer);