https://www.acmicpc.net/problem/21608
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
📌 작성한 코드
// 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]; // 좋아하는 친구 수에 따른 점수 추가
}
}
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript] 백준 골드 4 : 15683 - 감시 (1) | 2024.02.16 |
|---|---|
| [JavaScript] 백준 골드 5 : 21610 - 마법사 상어와 비바라기 (0) | 2024.02.13 |
| [JavaScript] 백준 골드 5 : 20055 - 컨베이어 벨트 위의 로봇 (1) | 2024.02.11 |
| [JavaScript] 백준 골드 4 : 16234 - 인구 이동 (1) | 2024.02.11 |
| [JavaScript] 백준 골드 5 : 14891 - 톱니바퀴 (1) | 2024.02.11 |