[알고리즘 풀이 분석] BOJ 21608 상어 초등학교

BOJ 21608 상어 초등학교

오랜만에 알고리즘 분석 포스팅이다! (맨날 오랜만임,,염병 ㅜ)
오늘은,, 이 아니고 거의 몇일에 거쳐서 구현 문제를 풀어보았다!
간단한거 하나 풀어서 시동 걸어보자는 마음으로 구현 문제를 골랐는데,, ㅋㅋㅋㅋㅋㅋ 너무 오래 걸렸다,,

오늘 푼 문제는 백준 21608 상어 초등학교 문제이다!

특별히 사용할 알고리즘도, 자료구조도 없지만
긴 지구력과 집중력이 필요함을 알게된 문제이다!

입출력

N*N 명의 학생들마다 좋아하는 친구들 번호가 주어지면
주어진 조건에 맞게 학생들을 자리에 앉힌 후 앉은 결과를 토대로 각 학생의 만족도를 구하는 문제이다.

이렇게 써놓고 보니 매우 간단한 문제인 것 같아 허무하다,,ㅎ,, 난 왜이리 오래 걸렸던 것인가

코드

문제 설명에 나와있는 것 처럼 1번 조건 체크 후 2번 조건, 3번 조건을 차례대로 체크하였다.

input으로 들어오는 선호도를 가지고 N*N 명의 학생들을 앉히는 큰 반복문 안에서 1번 조건 확인 후 자리가 결정되지 않으면 후보군을 가지고 2번 조건, 2번에서도 자리가 결정되지 않으면 3번 조건을 적용해 전역변수로 선언한 seat 배열에 학생을 앉혔다.

학생 앉히기

void sitStudents(int N, vector<pair<int, vector<int>>> preference, vector<pair<int, int>> & finalSeatOrder) {

    for(int i=0; i<preference.size(); i++) {
        int student = preference[i].first;
        vector<int> pref = preference[i].second;

        // 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
        vector<pair<int ,int>> candidates1 = checkCondition1(N, student, pref);

        // 1단계를 만족하는 자리가 하나일 때
        if (candidates1.size() == 1) {
            int R = candidates1[0].first;
            int C = candidates1[0].second;
            seat[R][C] = student;
            finalSeatOrder.push_back(make_pair(R, C));
            continue;
        }

        // 1단계를 만족하는 자리가 여러개일 때 candidates1 중에서 2단계 실행
        vector<pair<int, int>> candidates2 = checkCondition2(N, candidates1);
        if (candidates2.size() == 1) {
            int R = candidates2[0].first;
            int C = candidates2[0].second;
            seat[R][C] = student;
            finalSeatOrder.push_back(make_pair(R, C));
            continue;
        }

        // 2단계를 만족하는 자리가 여러개이면 candidates2 중에서 행, 열이 가장 작은 자리에 앉힘
        sort(candidates2.begin(), candidates2.end(), byRowCol);
        int finalR = candidates2[0].first;
        int finalC = candidates2[0].second;
        seat[finalR][finalC] = student;
        finalSeatOrder.push_back(make_pair(finalR, finalC));
    }

}

조건 1번 확인

vector<pair<int, int>> checkCondition1(int N, int student, vector<int> pref){
    // 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.

    vector<pair<int, int>> confirmedSeat;
    vector<pair<pair<int, int>, int>> friendCount;  // 각 자리별로 주변에 좋아하는 친구가 몇명 있는지

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (seat[i][j] == -1) { // 해당 자리가 빈 자리이면 좌우양옆 네 칸을 확인합니당

                int friends = 0;
                for (int k = 0; k < 4; ++k) {
                    int row = i + r[k];
                    int col = j + c[k];


                    if (isPrefStudents(N, row, col, pref)) { // 좋아하는 학생이 주변에 앉아있는 경우
                        friends++;
                    }
                }
                friendCount.push_back(make_pair(make_pair(i, j), friends));
            }
        }
    }

    // seatAndCount 를 second 값 기준으로 desc sort
    sort(friendCount.begin(), friendCount.end(), bySecondDesc);

    // 상위 n개 자리 추려서 return
    confirmedSeat.push_back((make_pair(friendCount[0].first.first, friendCount[0].first.second)));
    int max = friendCount[0].second;

    for (int i = 1; i < friendCount.size(); ++i) {
        if (friendCount[i].second == max) {
            confirmedSeat.push_back(make_pair(friendCount[i].first.first, friendCount[i].first.second));
        }else break;
    }

    return confirmedSeat;
}

조건 2번 확인

vector<pair<int, int>> checkCondition2(int N, vector<pair<int, int>> candidates1){
    vector<pair<pair<int, int>, int>> blankCount;
    vector<pair<int, int>> candidates2;

    for (int i = 0; i < candidates1.size(); ++i) {
        int blank = 0;
        for (int j=0; j<4; j++){
            // 인접 칸의 행, 열
            int row = candidates1[i].first + r[j];
            int col = candidates1[i].second + c[j];

            if (row>= 0 && row < N && col >=0 && col < N
                && seat[row][col] == -1) {  // 인접 칸이 비어 있으면 비어있는 칸 count
                blank++;
            }
        }
        blankCount.push_back(make_pair(candidates1[i], blank));
    }

    // 주변 칸 중 빈 칸이 많은 순으로 정렬
    sort(blankCount.begin(), blankCount.end(), bySecondDesc);

    // 상위 n 개 칸 추려서 return
    candidates2.push_back(blankCount[0].first);
    int max = blankCount[0].second;

    for (int i = 1; i < blankCount.size(); ++i) {
        if (blankCount[i].second == max){
            candidates2.push_back(blankCount[i].first);
        } else break;
    }

    return candidates2;
}

학생 만족도 조사

int getSatisfying(int N, vector<pair<int, vector<int>>> preference, vector<pair<int, int>> finalSeatOrder){
    int satisfied = 0;

    for (int i = 0; i < finalSeatOrder.size(); ++i) {
        int seatR = finalSeatOrder[i].first;
        int seatC = finalSeatOrder[i].second;
        vector<int> pref = preference[i].second;

        int friendCount = 0;
        // 각 자리 좌우양옆으로 좋아하는 친구 count
        for (int j = 0; j < 4; ++j) {
            int row = seatR + r[j];
            int col = seatC + c[j];

            if (isPrefStudents(N, row, col, pref)) {
                friendCount++;
            }
        }

        // 점수 더하기
        satisfied += points[friendCount];
    }

    return satisfied;
}

해당 칸에 좋아하는 친구가 있는지

bool isPrefStudents(int N, int row, int col, vector<int> pref){
    if (row>= 0 && row < N && col >=0 && col < N && seat[row][col] != -1){
        int neigh = seat[row][col];

        for (int i = 0; i < 4; ++i) {
            if (pref[i] == neigh) return true;
        }
    }
    return false;
}

코드가 많이 길어졌지만 조금 길어지더라도 차근차근 단계별로 정확하게 풀기위해 노력했다. 헷갈리지 않기 위해 인접 칸 인덱스 같은 경우도 일부러 변수에 풀어서 디버깅 과정에서 확인 하면서 진행했다.

물론 프로그래머스 상에서만 풀어야 할 경우도 대비를 해야겠지만..!
좀 더 간단히 줄일 수 있는 방법이 있는지 알아봐야겠다!