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

상어 초등학교

📚 문제 설명

N * N 의 좌석이 있고 학생들의 자리를 배치하려 한다.
학생 각각 자신이 좋아하는 친구가 있다.
자리 배치는 아래와 같은 원칙으로 배치한다고 했을 때,

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

자리 배치를 완료한 후에 학생들의 만족도의 총합을 구하여라.

학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.

👨🏻‍💻 풀이 과정

자리를 정할 학생 순서대로 입력이 주어진다고 했기 때문에 학생들은 순서대로 자리를 정해주면 될 것이다.

그럼 이제 자리에 관해서 생각해 봐야 한다.

• 친구와 가장 많이 인접한 자리가 최우선 순위이다.
• 그 중에서 빈칸과 많이 인접한 것.
• 왼쪽 맨위부터.

따라서 N * N 크기의 2차원 배열인 Map 배열을 만들어서 함수 SeatHappy를 이용해 각각의 자리에 점수를 매겼다.
빈자리가 인접할 경우 1점, 친구가 인접할 경우 10점.

그 후에 각각의 자리 중에서 점수가 가장 높은 자리를 배정해주면 될 것이다.

자리 배치 함수

	// 자리 점수 확인
    const SeatHappy = (x, y, prefer) => {
      	// 인접한 부분 위치
        const dir = [[1, 0], [-1, 0], [0, 1], [0, -1]];
      	// 인접한 빈칸
        let cnt = 0;
      	// 인접한 친구
        let friend = 0;
      	// 상하좌우 인접한 칸을 확인.
        for (const [dx, dy] of dir) {
          	// Map 밖으로 벗어나지 않도록
            if (x + dx < 0 || x + dx >= N || y + dy < 0 || y + dy >= N) continue;
          	// 빈칸, 친구 확인
            if (Map[x + dx][y + dy] === 0) {
                cnt += 1;
            }else if (prefer.includes(Map[x + dx][y + dy])) {
                friend += 1;
            }
        }
      	// 점수 리턴.
      	// 친구 점수의 경우 마지막 만족도를 위해 10의 거듭제곱으로 점수 계산.
        return friend === 0 ? cnt : (10** (friend)) + cnt;
    };
	// 자리 선택
    const SeatSelect = (StudentNumber, Prefer) => {
        let max = -1;
        let SeatX = -1;
        let SeatY = -1;
        for (let i = 0; i < Map.length; i++) {
            for (let j = 0; j < Map[0].length; j++) {
              	// 빈칸 중에서 정해야하기 때문.
                if (Map[i][j] === 0) {
                  	// 자리 점수.
                    let SeatPoint = SeatHappy(i, j, Prefer);
                  	// 최댓값 갱신.
                    if (max < SeatPoint) {
                        max = SeatPoint;
                        [SeatX, SeatY] = [i, j];
                    }
                }
            }
        }
      	// 자리 배치.
        Map[SeatX][SeatY] = StudentNumber;
    };

이제 학생들을 순서대로 자리를 배치하고 마지막에 만족도를 합하면 정답이다.
그런데 만족도 조사의 경우 이미 있는 SeatHappy 함수를 통해 알 수 있다.

전체 코드

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = parseInt(input.shift());
	// 친한 친구
    const StudentPrefer = input.map(v => v.split(' ').map(Number));
	// 2차원 좌석
    let Map = Array.from({length: N}, _ => Array(N).fill(0));
	// 자리 점수 확인
    const SeatHappy = (x, y, prefer) => {
      	// 인접한 부분 위치
        const dir = [[1, 0], [-1, 0], [0, 1], [0, -1]];
      	// 인접한 빈칸
        let cnt = 0;
      	// 인접한 친구
        let friend = 0;
      	// 상하좌우 인접한 칸을 확인.
        for (const [dx, dy] of dir) {
          	// Map 밖으로 벗어나지 않도록
            if (x + dx < 0 || x + dx >= N || y + dy < 0 || y + dy >= N) continue;
          	// 빈칸, 친구 확인
            if (Map[x + dx][y + dy] === 0) {
                cnt += 1;
            }else if (prefer.includes(Map[x + dx][y + dy])) {
                friend += 1;
            }
        }
      	// 점수 리턴.
      	// 친구 점수의 경우 마지막 만족도를 위해 10의 거듭제곱으로 점수 계산.
        return friend === 0 ? cnt : (10** (friend)) + cnt;
    };
	// 자리 선택
    const SeatSelect = (StudentNumber, Prefer) => {
        let max = -1;
        let SeatX = -1;
        let SeatY = -1;
        for (let i = 0; i < Map.length; i++) {
            for (let j = 0; j < Map[0].length; j++) {
              	// 빈칸 중에서 정해야하기 때문.
                if (Map[i][j] === 0) {
                  	// 자리 점수.
                    let SeatPoint = SeatHappy(i, j, Prefer);
                  	// 최댓값 갱신.
                    if (max < SeatPoint) {
                        max = SeatPoint;
                        [SeatX, SeatY] = [i, j];
                    }
                }
            }
        }
      	// 자리 배치.
        Map[SeatX][SeatY] = StudentNumber;
    };

    const solution = () => {
      	// 만족도
        let answer = 0;
      	// 선호도 객체
        let stdObj = {};
      	// 학생을 순차적으로 확인하며 좌석 선택.
        for (let i = 0; i < StudentPrefer.length; i++) {
            const [StdNum, ...Arr] = StudentPrefer[i];
            stdObj[StdNum] = Arr;
            SeatSelect(StdNum, Arr);
        }
      	// 전체 좌석을 확인 후 만족도 계산.
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < N; j++) {
              	// 만족도의 경우 10 ** (인접한 친구 - 1) 이다. 
              	// SeatHappy는 10 ** (인접한 친구) 이기 때문에 10으로 나누고, 빈칸 점수 때문에 버림을 진행해야 한다.
                answer += Math.floor(SeatHappy(i, j, stdObj[Map[i][j]]) / 10);
            }
        }
        console.log(answer);
    };
    solution();

🧐 후기

순차적으로 코드를 구현하다보니 생각보다 쉽게 풀렸던 문제였다.