[BOJ] 백준 21608 상어 초등학교

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

Approach

BFS + 완전탐색을 구현하는 문제이다.

▶ BFS (Breadth-First Search, 너비 우선 탐색) 

BFS (Breadth-First Search, 너비 우선 탐색)

 

① N * N 명의 친구들을 입력받은 순서대로 배치한다.

② 문제에서 주어진 우선순위에 따라 map[][]에 배치한다. → isBetterPosition()

    A) 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.

    B) 위 조건을 만족하는 칸이 여러 개이면, 

        인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.

    C) 위 조건까지 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 

         그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

③ 배치가 끝나고, 만족도 점수로 환산한다.

 

▶ |r1 - r2| + |c1 - c2| = 1 조건을 만족하려면 특정 칸에서 상/하/좌/우에 해당한다.

▶ 인접한 칸에 좋아하는 학생 수에 따른 만족도 점수는 분기문을 사용하기 보다는

    LUT (Lookup Table)를 사용해서 처리하였다.

ex) socre[1] = 1 = 인접한 칸에 좋아하는 학생이 한명 있을 때, 해당하는 만족도 점수

 

setStudents() 내용만 구현할 수 있다면 어렵지 않게 풀 수 있었던 문제이다. (주석 참고)

- 아직 학생이 배치되지 않은 비어있는 map[][] 

- 인접한 4칸에서 비어있는 칸의 개수

- 인접한 4칸에서 좋아하는 친구 수

- 위 조건을 만족하는 빈 칸 중 문제에서 주어진 우선순위가 가장 높은 곳

- N * N 의 배치만 끝나면, 나머지는 점수 환산을 쉽게 구현할 수 있다.

---

#include <stdio.h>
#define EMPTY 0

const int MAX_N = 20 + 2;
const int MAX_LIKE_FRIENDS = 4;
const int dx[] = { 1, -1, 0,  0 };
const int dy[] = { 0,  0, 1, -1 };
const int score[] = { 0, 1, 10, 100, 1000 };

struct Students
{
    int ID;
    int likeFriends[4];
}students[MAX_N * MAX_N];

struct Node
{
    int x, y; // map[][] 좌표
    int emptyCnt; // 근접한 빈 칸 개수
    int likeFriendsCnt; // 근접한 칸에서 좋아하는 친구 수

    void init(int _x = -1, int _y = -1)
    {
        x = _x, y = _y;
        emptyCnt = likeFriendsCnt = 0;
    }

    bool isEmpty()
    {
        return x == -1 || y == -1;
    }

}pivot, temp;
int N, ans, id;
int map[MAX_N][MAX_N], order[MAX_N * MAX_N];

void input()
{
    scanf("%d", &N);
    for (int i = 0; i < N * N; i++)
    {
        scanf("%d", &id); // 학생 번호
        students[id].ID = order[i] = id;
        for (int j = 0; j < MAX_LIKE_FRIENDS; ++j)
        {   // 해당 학생이 좋아하는 친구들 번호
            scanf("%d", &students[id].likeFriends[j]);
        }
    }
}

bool isBetterPosition()
{
    // 비교대상 (pivot)이 비어져 있는 경우
    if (pivot.isEmpty()) 
        return true;
    
    // 근접한 칸에 좋아하는 학생 수 비교 (보다 많은 것)
    if (temp.likeFriendsCnt > pivot.likeFriendsCnt)
    {
        return true;
    }
    else if (temp.likeFriendsCnt == pivot.likeFriendsCnt)
    {
        // 근접한 칸 중에 비어있는 칸 개수 비교 (보다 많은 것)
        if (temp.emptyCnt > pivot.emptyCnt)
        {
            return true;
        }
        else if (temp.emptyCnt == pivot.emptyCnt)
        {
            // 행 번호 비교 (보다 작은 것)
            if (temp.x < pivot.x)
            {
                return true;
            }
            else if (temp.x == pivot.x)
            {
                // 열 번호 비교 (보다 작은 것)
                if (temp.y < pivot.y)
                    return true;
            }
        }
    }
    return false;
}

void setStudents()
{
    for (int i = 0; i < N * N; i++)
    {       
        pivot.init();
        int sID = order[i];
        for (int x = 0; x < N; x++)
        {
            for (int y = 0; y < N; y++)
            {
                // 이미 학생이 놓여진 칸
                if (map[x][y] != 0)
                    continue;

                temp.init(x, y);
                for (int k = 0; k < 4; k++)
                {
                    int nextX = x + dx[k];
                    int nextY = y + dy[k];
                    if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N)
                        continue;
                    
                    // 근접한 칸이 비어있는 경우
                    if (map[nextX][nextY] == EMPTY)
                    {
                        temp.emptyCnt++;
                        continue;
                    }
                    
                    // 근접한 칸에 좋아하는 친구가 있는지 확인
                    for (int f = 0; f < MAX_LIKE_FRIENDS; f++)
                    {
                        if (students[sID].likeFriends[f] == map[nextX][nextY])
                        {
                            temp.likeFriendsCnt++;
                            break;
                        }
                    }
                }
                // 문제에서 주어진 우선순위에 따라 비교
                if (isBetterPosition())
                    pivot = temp;
            }
        }
        map[pivot.x][pivot.y] = sID;
    }
}

void getSatisfyScore()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int sID = map[i][j];
            int likeFriendCnt = 0;
            // 인접한 칸(상하좌우) 확인
            for (int k = 0; k < 4; k++)
            {
                int nextX = i + dx[k];
                int nextY = j + dy[k];
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N)
                    continue;

                // 좋아하는 학생에 해당하는지 확인
                for (int f = 0; f < MAX_LIKE_FRIENDS; f++)
                {
                    if (students[sID].likeFriends[f] == map[nextX][nextY])
                    {
                        likeFriendCnt++;
                        break;
                    }
                }
            }
            // 좋아하는 학생 수에 해당하는 만족도 점수로 전환
            ans += score[likeFriendCnt];
        }
    }
}

int main(void)
{
    // freopen("Input.txt", "r", stdin);
    input();
    setStudents();
    getSatisfyScore();
    printf("%d\n", ans);
    return 0;
}