[백준 21608] - 상어 초등학교(C++)[골드5]

문제

https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

---

🔎문제 설명

단순 구현 문제입니다.

조건이 굉장히 많고요. 하지만 문제를 차근차근 읽고, 경우의 수를 가지치기하면 쉽게 풀 수 있는 문제입니다.

 

💡주목해야 할 점

• 학생은 자신을 좋아할 수 없다.
• 인접한 칸의 정의는 기준칸에서 상하좌우 4방향이다.
• 자리를 결정하는 규칙이 3가지가 있다.
  1. 인접한 칸 내에서 좋아하는 학생이 가장 많은 칸으로 자리를 정합니다.
  2. 1번을 만족하는 칸이 여러 개라면, 인접하는 칸 중 비어있는 칸이 가장 많은 자리로 자리를 정합니다.
  3. 2번을 만족하는 칸이 여러개라면, 행의 번호가 가장 작은 칸, 그다음으로 열의 번호가 가장 작은 칸.
• 여기서 중요한 점은 (r,c)라면 r이 행이고, c가 열이라는 점입니다!

 

위 주목해야 할 점을 참고해서, 문제를 풀면 됩니다.

 

우선 각 학생별로 좋아하는 사람을 저장해야 합니다.

인접리스트를 통해서 저장했습니다.

p [번호]는 번호에 해당하는 학생이 좋아하는 학생들의 번호가 저장되어 있는 배열이 됩니다.

 

p [4][0]=2, p [4][1] = 5, p [4][2]= 1, p [4][3] =7  이런 식으로 저장되겠죠?

 

우선 입력제한을 보면 N의 크기가 그렇게 크지 않았기에 탐색을 위해 사용되는 2개의 배열을 사용했습니다.

탐색을 할 때마다 초기화해줬고, 첫 번째는 좋아하는 사람의 수를 저장하는 배열, 두 번째는 단순 비어있는 칸을 저장하는 배열입니다.

 

 

n*n으로 모든 칸을 탐색합니다.

기준 칸에서 4방향으로 탐색을하고, 4방향 중 비어있는 칸의 개수를 계산하고, 좋아하는 사람이 있는 칸의 개수를 계산합니다.

 

여기서 좋아하는 사람의 칸의 개수와 비어있는 칸의 개수를 최댓값으로 계속 갱신해 줍니다.

 

• 첫 번째로 좋아하는 사람의 칸수를 비교해 줍니다.(1번 조건)
  • 최댓값을 갱신한다면 좌표를 업데이트해 줍니다.
• 만약 좋아하는 사람의 수가 같다면 2번 조건을 검사합니다.
  • 최댓값을 갱신한다면 좌표를 업데이트해줍니다.
• 인접칸의 개수도 같다면, 3번 조건을 검사합니다.
  • 여기서는 행과 열이 가장 작은 자리가 선택됩니다.

 

여기서 max를 -1로 초기화해야 하는 이유에 대해서 설명해 드리겠습니다.

max가 0인 경우 만~~~ 약에 자리를 배치하다가 인접한 칸의 좋아하는 사람도 없고, 빈칸도 없는 경우가 분명히 생길 것입니다.

이러한 경우 mrow, mcol의 초기값인 (0,0)으로 배치되기에, 만약 (0,0)에 배치된 사람이 있다면 그 값을 덮어쓰기 때문에 반드시!!!

-1로 초기화해야 합니다.

저는 0으로 초기화해서, 런타임에러(인덱스 에러)가 발생했습니다..ㅠ

 

이렇게 자리 배치를 모두 완료하면, 만족도를 계산하면 됩니다.

만족도 계산은 굉장히 간단하기 때문에, 생략하겠습니다.

 

💻전체 코드

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<vector<int> > ary;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void find_blank(int idx, vector<int> p[]);
int main()
{
    cin >> n;
    ary.resize(n, vector<int>(n, 0));
    int score[5];
    score[0] = 0, score[1] = 1, score[2] = 10, score[3] = 100, score[4] = 1000;
    vector<int> p[n * n + 1];
    int idx, a;
    for (int i = 0; i < n * n; i++)
    {
        cin >> idx;
        for (int j = 0; j < 4; j++)
        {
            cin >> a;
            p[idx].push_back(a);
        }
        find_blank(idx, p);
    }
    int answer = 0,value=0,cnt=0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            value = ary[i][j];
            cnt = 0;  
            for (int k = 0; k < 4; k++) //인접칸 수 탐색
            {
                int nx = i + dir[k][0], ny = j + dir[k][1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                    continue;
                for (int z = 0; z < 4; z++) //인접칸 좋아하는 사람 탐색.
                {
                    if (ary[nx][ny] == p[value][z])
                        cnt++;
                }
            }
            answer += score[cnt];
        }
    }
    cout << answer << endl;

}
void find_blank(int idx, vector<int> p[])
{
    int v[n][n];
    int f[n][n];
    int max = -1, mrow = 0, mcol = 0, fcnt = 0, cnt = 0; //max값을 왜 -1로?
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (ary[i][j] != 0) //이미 들어있는 칸은 탐색할 필요가 없다.
                continue;
            cnt = 0;
            fcnt = 0;
            for (int d = 0; d < 4; d++)
            {
                int nx = i + dir[d][0], ny = j + dir[d][1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                    continue;
                if (ary[nx][ny] == 0)
                    cnt++;
                // cout<<"좋아하는 사람 찾기 "<<endl;
                for (int k = 0; k < 4; k++){
                    if (ary[nx][ny] == p[idx][k])// 좋아하는 놈일때.
                        fcnt++;
                }
            }
            v[i][j] = cnt;  // 인접칸수
            f[i][j] = fcnt; // 좋아하는 사람 칸수
            if (max < fcnt)
                max = fcnt, mrow = i, mcol = j;
            else if (max == fcnt)
            { // 만약 좋아하는 사람 칸수가 동일하다면
                if (v[i][j] > v[mrow][mcol])// 인접칸수중 비어있는 칸수를 비교함.
                    mrow = i, mcol = j;
                else if (v[i][j] == v[mrow][mcol])
                { // 인접칸수도 같다면, i가 작은거를 정함. j가 작은거를 정함.
                    if (i < mrow) // i가 작다면 바꿔줌.
                        mrow = i, mcol = j;
                    else if (i == mrow){ // i가 같을경우 j가 작은걸로 바꿔줌.
                        if (j < mcol)
                            mrow = i, mcol = j;
                    }
                }
            }
        }
    }
    ary[mrow][mcol] = idx;
}

 

 

😀느낀 점

• 문제가 길어서, 어려워 보이지만 차근차근 조건을 하나씩 가지치기하면 굉장히 쉬운 문제다.