[백준 21608][C++] 상어 초등학교

문제 링크

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

---

◆문제 해설 및 설명◆

 

문제 : 요약 불가...

쉽게 말해서 모든 칸의 상하좌우를 검색했을때, 1순위로 좋아하는 학생이 많은곳에 배치, 2순위로 빈칸이 많은곳에, 3순위로는 행의 번호가 작고 4순위로는 열의 번호가 작은 순 에 학생을 배치하면 된다.

 

구현문제이기 때문에 코드에서 설명을 이어가겠다.

 

◆코드 전문◆

#include <iostream>
using namespace std;
int map[20][20];
int favor[401][5];
int N, squareN, answer = 0;
int dy[4]{1, -1, 0, 0};
int dx[4]{0, 0, 1, -1};

int main()
{
    cin >> N;
    squareN = N * N;
    for (int i = 0; i < squareN; i++)
    {
        for (int k = 0; k < 5; k++)
        {
            cin >> favor[i][k];
        }
    }

    for (int i = 0; i < squareN; i++)
    {
        int maxFavorCount = -1, maxEmptyCount = -1;
        int Y = -1, X = -1;
        for (int r = 0; r < N; r++)
        {
            for (int c = 0; c < N; c++)
            {
                if (map[r][c] != 0)
                {
                    continue;
                }
                int favorCount = 0, emptyCount = 0;
                for (int dir = 0; dir < 4; dir++)
                {
                    int row = r;
                    int col = c;
                    row += dy[dir];
                    col += dx[dir];
                    if (row < 0 || col < 0 || row >= N || col >= N)
                    {
                        continue;
                    }
                    for (int F = 1; F < 5; F++)
                    {
                        if (map[row][col] == favor[i][F])
                        {
                            favorCount++;
                        }
                        else if (map[row][col] == 0)
                        {
                            emptyCount++;
                        }
                    }
                }
                if (maxFavorCount < favorCount)
                {
                    maxFavorCount = favorCount;
                    maxEmptyCount = emptyCount;
                    Y = r;
                    X = c;
                }
                if (maxFavorCount == favorCount && maxEmptyCount < emptyCount)
                {
                    maxEmptyCount = emptyCount;
                    Y = r;
                    X = c;
                }
            }
        }
        map[Y][X] = favor[i][0];
    }


    for (int r = 0; r < N; r++)
    {
        for (int c = 0; c < N; c++)
        {
            int favorCount = 0;
            for (int dir = 0; dir < 4; dir++)
            {
                int row = r;
                int col = c;
                row += dy[dir];
                col += dx[dir];
                if (row < 0 || col < 0 || row >= N || col >= N)
                {
                    continue;
                }

                for (int k = 0; k < squareN; k++)
                {
                    if (favor[k][0] == map[r][c])
                    {
                        for (int F = 1; F < 5; F++)
                        {
                            if (map[row][col] == favor[k][F])
                            {
                                favorCount++;
                            }
                        }
                    }
                }
            }
            if (favorCount == 1)
            {
                answer += 1;
            }
            else if (favorCount == 2)
            {
                answer += 10;
            }
            else if (favorCount == 3)
            {
                answer += 100;
            }
            else if (favorCount == 4)
            {
                answer += 1000;
            }
        }
    }
    cout << answer;
}

 

map 배열로 교실의 자리 정보를 저장하였다.

favor 배열을 통해 {favor[i][0] 번이 좋아하는 친구 favor[i][1], favor[i][2], favor[i][3] , favor[i][4] } 형식으로 저장하였다.

N은 입력받는 반의 한 줄의 크기를, squareN은 학생의 수를 저장한다.

dy, dx를 통해 반복문으로 상하좌우를 표현하였다.

#include <iostream>
using namespace std;
int map[20][20];
int favor[401][5];
int N, squareN, answer = 0;
int dy[4]{1, -1, 0, 0};
int dx[4]{0, 0, 1, -1};

 

입력을 받는 부분은 넘어가고, 학생을 배치하는 로직을 설명하겠다.

학생 수만큼 반복문을 실행해준다.

maxFavorCount는 임의의 좌표(Y,X)에 주변에 좋아하는 친구의 최대 갯수이고,

maxEmptyCount는 임의의 좌표(Y,X)에 주변에 비어있는 장소의 최대 갯수이다.

Y, X는 우선순위에 부합하는 위치를 저장하기 위해 쓰인다.

r, c매개변수를 통한 변수로 모든 칸을 검색하되 이미 자리의 주인이 있다면 continue한다.

    for (int i = 0; i < squareN; i++)
    {
        int maxFavorCount = -1, maxEmptyCount = -1;
        int Y = -1, X = -1;
        for (int r = 0; r < N; r++)
        {
            for (int c = 0; c < N; c++)
            {
                if (map[r][c] != 0)
                {
                    continue;
                }
                int favorCount = 0, emptyCount = 0;

 

favorCount와 emptyCount는 한 자리(칸)당 주변의 좋아하는 친구와 빈 자리의 수를 저장한다.

row와 col에 r,c좌표를 저장하고 상하좌우의 값을 반복문을 통해 탐색하여 친한 친구가 있을경우 favorCount++, 비어있을 경우 emptyCount++를 해주었다. (OutofBound를 막기 위한 조건절 포함)

                int favorCount = 0, emptyCount = 0;
                for (int dir = 0; dir < 4; dir++)
                {
                    int row = r;
                    int col = c;
                    row += dy[dir];
                    col += dx[dir];
                    if (row < 0 || col < 0 || row >= N || col >= N)
                    {
                        continue;
                    }
                    for (int F = 1; F < 5; F++)
                    {
                        if (map[row][col] == favor[i][F])
                        {
                            favorCount++;
                        }
                        else if (map[row][col] == 0)
                        {
                            emptyCount++;
                        }
                    }
                }

 

 

한칸을 검사하고 1순위 조건인 친한 친구가 많다면 maxFavorCount, maxEmptyCount, Y와 X값을 갱신한다.

1순위는 같지만 빈자리가 많다면(2순위), maxEmptyCount, Y와 X값을 갱신한다.

3순위는 어차피 행열의 시작이 (0,0)인 이상 지켜지게 되있다.

그리고 모든 칸을 검사하고 favor[i][0] 친구를 map[Y][X]에 배치하고 다음 친구를 배치하기 위해 반복문 상단으로 이동한다.

 

                if (maxFavorCount < favorCount)
                {
                    maxFavorCount = favorCount;
                    maxEmptyCount = emptyCount;
                    Y = r;
                    X = c;
                }
                if (maxFavorCount == favorCount && maxEmptyCount < emptyCount)
                {
                    maxEmptyCount = emptyCount;
                    Y = r;
                    X = c;
                }
            }
        }
        map[Y][X] = favor[i][0];
    }

 

학생의 배치가 전부 마쳤다면, 상하좌우를 검사하여 친한친구의 갯수 만큼 점수를 더해주고 출력한다.

    for (int r = 0; r < N; r++)
    {
        for (int c = 0; c < N; c++)
        {
            int favorCount = 0;
            for (int dir = 0; dir < 4; dir++)
            {
                int row = r;
                int col = c;
                row += dy[dir];
                col += dx[dir];
                if (row < 0 || col < 0 || row >= N || col >= N)
                {
                    continue;
                }

                for (int k = 0; k < squareN; k++)
                {
                    if (favor[k][0] == map[r][c])
                    {
                        for (int F = 1; F < 5; F++)
                        {
                            if (map[row][col] == favor[k][F])
                            {
                                favorCount++;
                            }
                        }
                    }
                }
            }
            if (favorCount == 1)
            {
                answer += 1;
            }
            else if (favorCount == 2)
            {
                answer += 10;
            }
            else if (favorCount == 3)
            {
                answer += 100;
            }
            else if (favorCount == 4)
            {
                answer += 1000;
            }
        }
    }

    cout << answer;
}