[백준 BOJ] 21608번 - 상어 초등학교 (C++)

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

삼성 SW 역량 테스트 기출 문제

21608번: 상어 초등학교 | 문제 바로가기

문제풀이 (2022-01-31 MON 💻)

🤔 사담

오늘이야말로 찐 사담 오브 사담-!

아기상어, 청소년상어, 상어초등학교.. 벌써 상어 등장하는 문제만 세 번째..! 뚜둥!
머릿 속에서 브금으로 아기~상어~ 뚜루룻뚜루~ 귀여운~ 뚜루룻뚜루~ 자동으로 울려퍼짐 🎵
강아지도 있고 고냥이도 있고 많은데 상어가 단골로 등장하는지 궁금 👀

⭐ 풀이의 핵심

전형적인 단순 구현 문제였다!
구현 문제는 조건을 빼먹지 않는 게 중요해서
다른 문제들보다 더더욱 주석을 열심히 다는 편이다

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

👉 특히 이런 식으로 주어진 조건들은 그대로 복붙해서 해당 부분에 주석으로 넣어두는 편!

🚨 간과 또는 실수한 부분

오랜만에 (?) 런타임에러(OutOfBounds)을 마주하게 되었다 🤦‍♀️

// like[i]: i번 학생이 좋아하는 학생의 번호들을 담은 벡터
vector<vector<int>> like(401, vector<int>());

// seat[i]: i번 학생의 정해진 자리 행렬 인덱스 (미정일 경우 (-1, -1))
vector<pair<int, int>> seat(401, {-1, -1});

// map[i][j]: (i,j) 자리에 앉은 학생의 번호 (배정된 학생이 없을 경우 -1)
vector<vector<int>> map(20, vector<int>(20, -1));

기본적으로 이렇게 세 개의 전역 변수 vector를 선언하고 시작했는데

• 학생의 번호 인덱스는 문제에 제시된대로 1~N을 사용
• 자리의 행렬 인덱스는 문제에 제시된 것과 달리 (0,0)~(N-1,N-1)을 사용
  (ex. 문제에서 설명한 (2,2) == 나의 코드에서 (1,1)로 처리)

해서 나도 왜 이렇게 했는지 모르겠다..
다음부턴 0부터 시작할지 1부터 시작할지 통일하는 게 혼란스럽지 않을듯.. 머쓱
뭔가 전역변수들 범위를 잘못 지정해줬나 살펴봤는데 아니었고....
(혹시나 해서 vector<vector<int>> map(21, vector<int>(21, -1)); 로 고쳐줬는데
역시나 이 문제가 아니었음)

중간에 후보 자리들을 담는 데 사용한
candidatesVec1, candidatesVec2 벡터의 초기화에 문제가 있었다
조건이 연쇄적으로 있을 때 중간중간 임시적으로 값을 담아두는 변수들에 대해
좀 더 세심하게 고민할 필요가 있을 것 같다..!

cf) 디버깅에 결정적 힌트가 된 테스트케이스
[출처] https://jamluck.tistory.com/5 감사합니다 🙏
> 입력
3
1 2 3 4 5
2 1 3 4 5
3 1 2 4 5
4 1 2 3 5
5 1 2 3 4
6 1 2 3 4
7 1 2 3 4
8 1 2 3 4
9 1 2 3 4
> 출력
134
> 자리 배치 완성 결과 (참고)
4 2 7
3 1 5
8 6 9

👉 candidatesVec1 해결

// 1번 조건에 따른 후보 자리의 행렬 인덱스를 담는 벡터
vector<pair<int, int>> candidatesVec1; 
for (int i=0; i<N; i++) {
	for (int j=0; j<N; j++) {
        if (map[i][j] == -1) {
            candidatesVec1.push_back({i, j});
        }
    }
}

처음에는 백준 테케 1번의 4번 학생처럼
첫 번째 자리 배치 대상이라 좋아하는 학생 4명의 자리가 모두 미정일 때만 고려하여
모든 칸이 candidatesVec1에 들어가야 한다는 생각으로
if 문 없이 (0,0)~(N-1,N-1) 행렬 인덱스를 모두 candidatesVec1에 넣어줬었다

🔥 BUT!
첫 번째 대상이 아니고 몇몇 다른 학생들이 자리를 배치 받은 상태에서
좋아하는 학생 4명의 자리가 모두 미정이거나
좋아하는 학생 4명과 전부 인접하게 앉을 수 없는 상태일 수도 있기 때문에
모든 칸이 아니라 남은 빈 칸만 candidatesVec1에 들어가도록 if문을 추가해야 했다

👉 candidatesVec2 해결

// 2번 조건에 따른 후보 자리의 행렬 인덱스를 담는 벡터
vector<pair<int, int>> candidatesVec2(candidatesVec1); 

처음에는 candidatesVec2를 빈 벡터로 초기화해줬었다

🔥 BUT!
candidatesVec1에 있는 후보 자리들 중
인접한 칸이 빈 칸인 자리가 하나도 없을 수 있고
그런 경우에는 2번 조건이 아닌 3번 조건에 의해 자리가 결정될 수 있도록 해야하며
3번 조건은 candidatesVec2를 기준으로 정렬을 진행하기 때문에
candidatesVec2는 candidatesVec1을 복사하여 초기화해주어야 했다

🔽 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int N; // cf) 3 <= N <= 20
vector<vector<int>> like(401, vector<int>());
vector<pair<int, int>> seat(401, {-1, -1});
vector<vector<int>> map(21, vector<int>(21, -1));

// 위 오른쪽 아래 왼쪽
int dR[4] = {-1, 0, 1, 0};
int dC[4] = {0, 1, 0, -1};

/*
void printMap() {
    cout << "printMap" << endl;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
*/

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
    // cf) 3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
    if (a.first == b.first) {
        return a.second < b.second;
    }
    return a.first < b.first;
}

void selectSeat(int idx, vector<int> likeList) {
    vector<vector<int>> candidatesMap(21, vector<int>(21, 0)); // 후보 자리에 조건에 따라 점수를 매겨 점수가 가장 높은 자리로 선택
    vector<pair<int, int>> candidatesVec1; // 1번 조건에 따른 후보 자리의 행렬 인덱스를 담는 벡터
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (map[i][j] == -1) {
                candidatesVec1.push_back({i, j});
            }
        }
    }
    int maxScore = 0; // 후보 점수 중 최댓값

    // cf) 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
    // idx번 학생이 좋아하는 학생 4명 자리에 대해 반복 
    for (int i=0; i<4; i++) {
        pair<int, int> likeSeat = seat[likeList[i]]; // 좋아하는 학생의 자리
        
        // 좋아하는 학생의 자리가 아직 미정일 경우 continue 
        if (likeSeat.first == -1) { continue; }

        // 좋아하는 학생의 자리의 인접한 칸 탐색
        for (int j=0; j<4; j++) {
            int row = likeSeat.first + dR[j];
            int col = likeSeat.second + dC[j];

            // 인접한 자리가 교실 범위 밖이거나 빈 자리가 아닐 경우 continue 
            if (row < 0 || row >= N || col < 0 || col >= N || map[row][col] != -1) { continue; }

            // 그 외 자리에 대해서 후보 점수 증가
            candidatesMap[row][col]++;

            // 해당 자리의 후보 점수가 maxScore보다 클 경우
            if (candidatesMap[row][col] > maxScore) {
                // 해당 점수로 maxScore 변경하고
                // candidatesVec1 비우고 해당 자리만 후보로 push
                maxScore = candidatesMap[row][col];
                candidatesVec1.clear();
                candidatesVec1.push_back({row, col});
            }
            // 해당 자리의 후보 점수가 maxScore과 같을 경우
            else if (candidatesMap[row][col] == maxScore) { 
                // candidatesVec1에 해당 자리도 후보로 push
                candidatesVec1.push_back({row, col});
            }
        }
    }

    // 1번 조건에 의해 결정
    if (candidatesVec1.size() == 1) { 
        seat[idx] = {candidatesVec1[0].first, candidatesVec1[0].second};
        map[candidatesVec1[0].first][candidatesVec1[0].second] = idx; 
    }
    
    // cf) 2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
    else {
        vector<pair<int, int>> candidatesVec2(candidatesVec1); // 2번 조건에 따른 후보 자리의 행렬 인덱스를 담는 벡터
        
        // 1번 조건을 통해 필터링 된 후보 자리에 대해 반복 
        for (int i=0; i<candidatesVec1.size(); i++) {
            // 후보 자리
            int row = candidatesVec1[i].first;
            int col = candidatesVec1[i].second;

            // 후보 자리의 인접한 자리 탐색
            for (int j=0; j<4; j++) {
                int adjRow = row + dR[j];
                int adjCol = col + dC[j];

                // 인접한 자리가 범위 내에 있고 빈 자리일 경우 
                if (adjRow >= 0 && adjRow < N && adjCol >= 0 && adjCol < N && map[adjRow][adjCol] == -1) {
                    // 후보 자리에 대해서 후보 점수 증가
                    candidatesMap[row][col]++;

                    // 해당 자리의 후보 점수가 maxScore보다 클 경우
                    if (candidatesMap[row][col] > maxScore) {
                        // 해당 점수로 maxScore 변경하고
                        // candidatesVec2 비우고 해당 자리만 후보로 push
                        maxScore = candidatesMap[row][col];
                        candidatesVec2.clear();
                        candidatesVec2.push_back({row, col});
                    }
                    // 해당 자리의 후보 점수가 maxScore과 같을 경우
                    else if (candidatesMap[row][col] == maxScore) {    
                        // candidatesVec2에 해당 자리도 후보로 push
                        candidatesVec2.push_back({row, col});
                    }
                }
            }
        }

        // 2번 조건에 의해 결정
        if (candidatesVec2.size() == 1) { 
            seat[idx] = {candidatesVec2[0].first, candidatesVec2[0].second};
            map[candidatesVec2[0].first][candidatesVec2[0].second] = idx;
        }
        
        // 3번 조건에 의해 결정 (cmp 함수 참고)
        else { 
            sort(candidatesVec2.begin(), candidatesVec2.end(), cmp);
            seat[idx] = {candidatesVec2[0].first, candidatesVec2[0].second};
            map[candidatesVec2[0].first][candidatesVec2[0].second] = idx;
        }
    }

    // 자리 배치 종료 후 만족도를 구하기 위해 like 벡터에 likeList 저장
    like[idx] = likeList;
}

int satisfaction(int num) { // num은 학생의 수
    int answer = 0;
    for (int i=1; i<=num; i++) {
        int row = seat[i].first;
        int col = seat[i].second;

        // cf) 학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 
        int count = 0;
        for (int j=0; j<4; j++) {
            int adjRow = row + dR[j];
            int adjCol = col + dC[j];

            if (adjRow < 0 || adjRow >= N || adjCol < 0 || adjCol >= N) { continue; }
            if (find(like[i].begin(), like[i].end(), map[adjRow][adjCol]) != like[i].end()) { count++; }
        }

        // cf) 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.
        if (count != 0) {
            answer += pow(10, count-1);
        }
    }

    return answer;
}

int main() {
    // 입력
    scanf("%d", &N);
    int num = N * N; // num은 학생의 수

    int idx;
    for (int i=0; i<num; i++) {
        scanf("%d", &idx);

        int likeIdx;
        vector<int> likeList;
        for (int i=0; i<4; i++) {
            scanf("%d", &likeIdx);
            likeList.push_back(likeIdx);
        }

        // 자리 배치
        selectSeat(idx, likeList);
    }

    // 만족도 구하기
    int answer = satisfaction(num);

    //출력
    printf("%d", answer);

    return 0;
}