[JavaScript] 백준 골드 5 : 21608 - 상어 초등학교

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

21608번: 상어 초등학교

---

📌 작성한 코드 

// 21608
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const list = input.map((str) => str.split(" ").map(Number));

// 1. 비어있는 칸 중 좋아하는 학생이 가장 많이 인접한 칸을 저장
// 2. 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 저장
// 3. 행의 번호가 가장 작은 칸, 열의 번호가 가장 작은 칸으로 자리를 정함

const board = Array.from({ length: N }, () => new Array(N).fill(0));

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

for (let i = 0; i < N ** 2; i++) {
    const [student, ...likes] = list[i];
    let [likeCount, emptyCount, row, col] = new Array(4).fill(-1);

    for (let x = 0; x < N; x++) {
        for (let y = 0; y < N; y++) {
            if (board[x][y] !== 0) continue;

            let tempLikeCount = 0;
            let tempEmptyCount = 0;

            for (let l = 0; l < 4; l++) {
                const nx = x + dx[l];
                const ny = y + dy[l];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if (likes.includes(board[nx][ny])) tempLikeCount++;
                if (board[nx][ny] === 0) tempEmptyCount++;
            }

            if (tempLikeCount > likeCount) {
                likeCount = tempLikeCount;
                emptyCount = tempEmptyCount;
                row = x;
                col = y;
            } else if (tempLikeCount === likeCount) {
                if (tempEmptyCount > emptyCount) {
                    likeCount = tempLikeCount;
                    emptyCount = tempEmptyCount;
                    row = x;
                    col = y;
                }
            }
        }
    }
    board[row][col] = student;
}

const scores = [0, 1, 10, 100, 1000];
let answer = 0;

for (let x = 0; x < N; x++) {
    for (let y = 0; y < N; y++) {
        let tempScore = 0;
        const studentInfo = list.find((val) => val[0] === board[x][y]);
        const likes = studentInfo ? studentInfo.slice(1) : [];

        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) continue;
            if (likes.includes(board[nx][ny])) {
                tempScore++;
            }
        }

        answer += scores[tempScore];
    }
}

console.log(answer);

📌 풀이 

학생과 학생들이 좋아하는 학생이 저장된 배열을 순회하면서 어떤 자리가 가장 높은 점수를 얻을 수 있는지 확인하고, 해당 자리에 학생을 배치해야 한다.

 

학생을 배치하는 조건 

1. 비어있는 칸 중 좋아하는 학생이 가장 많이 인접한 칸을 저장
2. 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 저장
3. 행의 번호가 가장 작은 칸, 열의 번호가 가장 작은 칸으로 자리를 정함

 

(1) 학생 배치하기

이중 포문을 돌면서 각 위치에 방문해보고, 이미 다른 학생이 앉은 상태라면 다음 자리로 넘어간다.

  if (board[x][y] !== 0) continue;

현재 방문한 위치에서 상하좌우를 확인하고, 해당 위치에 좋아하는 학생이 몇명 있는지, 비어있는 자리가 몇자리 있는지 확인하고 기록한다. (`tempLikeCount`, `tempEmptyCount`). 이를 구한 다음에 학생을 배치하는 조건을 확인해 본다.

for (let l = 0; l < 4; l++) {
    const nx = x + dx[l];
    const ny = y + dy[l];

    if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
    if (likes.includes(board[nx][ny])) tempLikeCount++;
    if (board[nx][ny] === 0) tempEmptyCount++;
}

1. 현재 좋아하는 학생과 인접한 수가 이전에 저장된 수보다 큰가? -> 해당 자리가 더 좋은 조건이므로 해당 자리를 저장 

2. 좋아하는 학생 수는 같은데 빈 자리가 더 많은가? -> 해당 자리가 더 좋은 조건이므로 해당 자리를 저장 

3. 좋아하는 학생 수도 같고, 빈자리도 같은 경우에는 행과 열의 번호가 더 작은 위치에 배치해야 하는데 그렇다면 이전에 저장된 자리가 더 좋은 조건이므로 그대로 둠

이러한 조건 이외의 경우에는 좋은 자리가 아니므로 해당 자리에 학생을 배치하지 않아야 하니 값을 업데이트 시키지 않는다. 

if (tempLikeCount > likeCount) { // 1. 좋아하는 친구 수가 더 많을 때 업데이트
    likeCount = tempLikeCount;
    emptyCount = tempEmptyCount;
    row = x;
    col = y;
} else if (tempLikeCount === likeCount) { // 2. 좋아하는 친구 수가 같고 빈자리 더 많을 때 업데이트
    if (tempEmptyCount > emptyCount) {
        likeCount = tempLikeCount;
        emptyCount = tempEmptyCount;
        row = x;
        col = y;
    }
}

이렇게 모든 자리를 확인하고 나면 `row`와 `col`에 가장 좋은 자리의 좌표가 저장되어 있을 것이다. 해당 자리에 학생을 배치시킨다. 

(* 이때 주의해야 할 점은 likeCount, emptyCount, row, col을 0으로 초기화 하면 안된다. 그렇게 되면 좋은 자리를 찾지 못했을 경우 0번에 자리가 있어도 해당 자리에 학생을 배치시키는 오류가 발생한다.) 

board[row][col] = student;

 

(2) 학생 만족도 구하기

모든 학생을 배치시킨 후에 모든 좌표를 돌면서 해당 좌표가 몇점인지 구한다. 상하좌우를 확인하여 좋아하는 친구의 수를 세고, 그 값에 해당하는 점수를 더해준다. 

const scores = [0, 1, 10, 100, 1000];
let answer = 0;

for (let x = 0; x < N; x++) {
    for (let y = 0; y < N; y++) {
        let tempScore = 0;
        const studentInfo = list.find((val) => val[0] === board[x][y]);
        const likes = studentInfo ? studentInfo.slice(1) : []; // studentInfo가 존재하는지 확인해줘야 타입에러 발생하지 않음

        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) continue;
            if (likes.includes(board[nx][ny])) { // 좋아하는 친구 있으면 추가
                tempScore++;
            }
        }

        answer += scores[tempScore]; // 좋아하는 친구 수에 따른 점수 추가
    }
}

✅ 성공