백준 21608 상어 초등학교 (C++)

21608번: 상어 초등학교

로직을 구현하는 문제이다. 문제에 있는 3가지 단계를 직접 구현을 해주면 된다. 학샏 수 만큼 반복문을 돌며 이를 3가지 step으로 나누어 진행하였다. 각 step마다 자리 전체를 반복문을 돌며 각 조건에 맞을 경우를 count하여 이 때의 위치를 v[count]에 넣은 후 count가 많은 위치부터 체크를 하여 값이 여러 개일 경우 다음 step으로 넘어가도록 해주었다. 후에 sumScore를 통해 score를 구해 출력해주었다. 생각보다 시간이 걸린 문제였다. 범위를 잘못 설정해 계속해서 OutOfBound가 발생했었다. 확실히 범위를 체크하자.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, result = 0;
int A[400];
int B[400][4];
int seat[20][20];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
vector<pair<int, int>> v[5];
vector<pair<int, int>> v2[5];
int tmp = -1;
int tmp2 = -1;
int score[5] = { 0,1,10,100,1000 };

void step1(int n) {
    for (int i = 0; i < 5; i++) {
        v[i].clear();
    }
    tmp = -1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (seat[i][j] != 0) continue;

            int count = 0;
            for (int k = 0; k < 4; k++) {
                int ny = i + dy[k];
                int nx = j + dx[k];

                if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;

                for (int l = 0; l < 4; l++) {
                    if (seat[ny][nx] == B[n][l]) count++;
                }
            }

            v[count].push_back({ i,j });
        }
    }

    for (int i = 4; i >= 0; i--) {
        if (v[i].empty()) continue;

        if (v[i].size() == 1) {
            int y = v[i].front().first;
            int x = v[i].front().second;

            seat[y][x] = A[n];
            break;
        }
        else {
            tmp = i;
            break;
        }
    }
}

void step2(int n) {
    for (int i = 0; i < 5; i++) {
        v2[i].clear();
    }
    tmp2 = -1;

    for (int i = 0; i < v[tmp].size(); i++) {
        int count = 0;
        int y = v[tmp][i].first;
        int x = v[tmp][i].second;

        for (int j = 0; j < 4; j++) {
            int ny = y + dy[j];
            int nx = x + dx[j];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;

            if (seat[ny][nx] == 0) count++;
        }

        v2[count].push_back({ y,x });
    }

    for (int i = 4; i >= 0; i--) {
        if (v2[i].empty()) continue;

        if (v2[i].size() == 1) {
            int y = v2[i].front().first;
            int x = v2[i].front().second;

            seat[y][x] = A[n];
            break;
        }
        else {
            tmp2 = i;
            break;
        }
    }
}

void step3(int n) {
    sort(v2[tmp2].begin(), v2[tmp2].end());

    int y = v2[tmp2].front().first;
    int x = v2[tmp2].front().second;

    seat[y][x] = A[n];
}

void sumScore() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int num = 0;
            int count = 0;

            for (int k = 0; k < N * N; k++) {
                if (seat[i][j] == A[k]) {
                    num = k;
                    break;
                }
            }

            for (int k = 0; k < 4; k++) {
                int ny = i + dy[k];
                int nx = j + dx[k];

                if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;

                for (int l = 0; l < 4; l++) {
                    if (seat[ny][nx] == B[num][l]) count++;
                }
            }

            result += score[count];
        }
    }
}

void solution() {
    seat[1][1] = A[0];

    for (int i = 1; i < N * N; i++) {
        step1(i);

        if (tmp == -1) continue;
        step2(i);

        if (tmp2 == -1) continue;
        step3(i);
    }

    sumScore();

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N * N; i++) {
        cin >> A[i];

        for (int j = 0; j < 4; j++) {
            cin >> B[i][j];
        }
    }

    solution();

    return 0;
}