[삼성기출] 백준 - C++ 상어 초등학교

BFS와 시뮬레이션 문제이다.

 

풀이

-

---

1. Solution 코드

#include <stdio.h>

const int MAX_N = 20;
const int EMPTY = 0;
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;
}

 

 

2. 알아야 할 개념

1) 구현 아이디어

•  1. for문으로 대상을 비교할 수도 있지만, 변수를 새로 선언해서 비교하자                                                     2. 조건문으로 특정 행위를 하고 싶다면? return을 활용하자

  bool IsBetterPosition() {
  	// 비교대상(pivot)이 비어져 있는 경우
  	if (pivot.isEmpty())
  		return true;
  
  	// 조건1) 근접한 칸에 좋아하는 학생 수 비교
  	if (temp.likeFriendCnt > pivot.likeFriendCnt)
  		return true;
  	else if (temp.likeFriendCnt == pivot.likeFriendCnt) {
  		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;
  }​

• 3. continue, break 를 적극 활용하자

void SetStudents() {
	for (int i = 0; i < N * N; i++) {
		pivot.init();
		int sID = order[i];

		for (int x = 0; i < N; i++) {
			for (int y = 0; y < N; y++) {
				// 이미 학생이 놓여진 칸
				if (map[x][y] != 0)
					continue;

				temp.init(x, y);
				for (int dir = 0; dir < 4; dir++) {
					int nextX = x + dx[dir];
					int nextY = y + dy[dir];
					if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N)
						continue;

					// 근접한 칸이 비어있는 경우
					if (map[nextX][nextY] == EMPTY) {
						temp.emptyCnt++;
						continue;
					}

					// 근접한 칸에 좋아하는 친구가 있는지
					for (int f = 0; f < 4; f++) {
						if (students[sID].likeFriends[f] == map[nextX][nextY]) {
							temp.likeFriendCnt++;
							break;
						}
					}
				}

				// 문제에서 주어진 우선순위에 따라 비교
				if (IsBetterPosition())
					pivot = temp;
			}
		}
		map[pivot.x][pivot.y] = sID;
	}
}