[BOJ] 백준 23291 어항 정리

Approach

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

문제 난이도는 다른 시간 2번 문제와 비슷하지만

디버깅 관점에서는 보다 쉬운 문제인 것 같다.

📌 [BOJ] 23289 온풍기 안녕! 

[BOJ] 백준 23289 온풍기 안녕!

 

어항이 변화되는 규칙을 빠르게(?) 파악한다면

테스트 결과로도 좋지 않았을까,,,😏

다른 문제도 함께 참고해보세요.

📌 삼성 SW 기출 모음

---

int main()
{
       // freopen("input.txt", "r", stdin);
       input();
       while (1)
       {
              addFish();           // 1. 물고기 추가

              roll();              // 2. 어항 쌓기
              controlFish();       // 3. 물고기 수 조절
              sortFish();          // 4. 물고기 정렬

              fold();              // 5. 어항 접기
              controlFish();       // 6. 물고기 수 조절
              sortFish();          // 7. 물고기 정렬

              ans++;               // 8. 정리 횟수
              if (getDiff() <= K) break;
       }
       printf("%d\n", ans);
}

문제에서 요구하는 조건을 모듈화 한다면 디버깅하기 좋다.

[3, 4]와 [6, 7]은 동일한 map[][] 형태가 나오도록 설계한다.

 

각 모듈 중간에 map[][] 상태 출력은

아래 함수를 이용해보자.

void printMap()
{
       for (int x = 1; x <= N; x++)
       {
              for (int y = 1; y <= N; y++)
              {
                     printf("%3d ", map[x][y]);
              }
              puts("");
       }
       puts("");
}

---

1. 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다.

   만약, 그러한 어항이 여러개라면

   물고기의 수가 최소인 어항 모두에 한 마리씩 넣는다.

vector를 이용해서 최소값에 해당하는 어항을 모두 저장한다.

어항들을 비교하면서 최소값이 갱신되면 vector도 같이 갱신

void addFish()
{
       vector<Node> vec;
       int minVal = MAX;
       for (int x = 1; x <= N; x++)
       {
              for (int y = 1; y <= N; y++)
              {
                     if (map[x][y] == EMPTY)
                           continue;

                     // 최소값에 해당하는 어항 찾기
                     if (map[x][y] < minVal)
                     {
                           minVal = map[x][y];
                           vec.clear();
                           vec.push_back({ x, y });
                     }

                     // 같은 최소값을 가지고 있는 어항인 경우
                     else if (map[x][y] == minVal)
                     {
                           vec.push_back({ x, y });
                     }
              }
       }

       for (int i = 0; i < vec.size(); ++i)
       {
              map[vec[i].x][vec[i].y]++;
       }
}

---

2. 어항을 쌓는다.

    • 가장 왼쪽에 있는 어항을 그 어항의 오른쪽에 있는 어항의 위에 올려 놓는다.

    • 2개 이상 쌓여있는 어항을 모두 공중 부양시킨 다음, 

        전체를 시계방향으로 90도 회전시킨다.

        이후, 공중 부양시킨 어항을 바닥에 있는 어항의 위에 올려놓는다.

    • 바닥의 가장 왼쪽에 있는 어항 위에 공중 부양시킨 어항 중

        가장 왼쪽에 있는 어항이 있어야 한다.

    • 이 작업은 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 

        바닥에 있는 어항이 있을때까지 반복한다.

 

해당 문제에서 규칙 파악과 구현하기 까다로운 기능이다. 🤔

• 어항을 회전하면서 쌓기

 

김밥이 돌돌 말리듯 어항이 쌓이는데,

시작위치인 pivot과 w(너비) h(높이)는 일정한 규칙이 있다.

• pivot : 1    2    3    5    7    10    …

• w : 1    1    2    2    3    3    …

• h : 1    2    2    3    3    4    …

→ 어항이 쌓이는 형태를 보면 w, h 는 번갈아가며 증가한다.

→ pivot은 idx / 2 + 1 수치로 변화한다.

→ 90° 회전은 아래 글 참고해서 구현 가능

행렬 90° 회전 (C 언어)

 

• 언제까지 회전 시킬까?

문제 예시로 보여준 것을 보기 쉽게 표현하면

pivot-1 + w + h > N 일 때, 더이상 쌓을 수 없다.

void roll()
{
       int pivot, w, h;
       pivot = w = h = 1;
       for (int idx = 0; ; ++idx)
       {
              if (pivot - 1 + w + h > N)
                     break;
              for (int c = pivot; c < pivot + w; c++)
              {
                     for (int r = N; r > N - h; r--)
                     {
                           int nextR = (N - w) + (c - pivot);
                           int nextC = (pivot + w) + (N - r);
                           map[nextR][nextC] = map[r][c];
                           map[r][c] = EMPTY;
                     }
              }
              pivot += (idx / 2 + 1);
              idx % 2 ? w++ : h++;
       }
}

---

3. 어항에 있는 물고기 수 조절

    • 모든 인접한 두 어항에 대해서, 물고기 수의 차이를 구한다.

    • 이 차이를 5로 나눈 몫을 d라고 하자.

        d가 0보다 크면, 두 어항 중 물고기의 수가 

        많은 곳에 있는 물고기 d 마리를 적은 곳에 있는 곳으로 보낸다.

    • 이 과정은 모든 인접한 칸에 대해서 동시에 발생한다.

• 인접한 상하좌우 탐색을 위해서 BFS 탐색방식으로 구현한다.

    • map[][]의 범위가 1~N 이므로 범위로 설정하였기에

        범위를 벗어나는 경우는 고려하지 않는다.

• 동시에 물고기 이동이 발생하므로 별도의 map[][] 이용

void controlFish()
{
       int cMap[MAX_N][MAX_N] = { 0 };

       for (int x = 1; x <= N; x++)
       {
              for (int y = 1; y <= N; y++)
              {
                     if (map[x][y] != EMPTY)
                     {
                           cMap[x][y] += map[x][y];
                           for (int d = 0; d < 4; d++)
                           {
                                  int nextX = x + dx[d];
                                  int nextY = y + dy[d];
                                  if (map[nextX][nextY] == EMPTY)
                                         continue;

                                  // 물고기가 많은 경우
                                  if (map[x][y] > map[nextX][nextY])
                                  {
                                         int diff = (map[x][y] -  map[nextX][nextY]) / 5;
                                         cMap[x][y] -= diff;
                                         cMap[nextX][nextY] += diff;
                                  }
                           }
                     }
              }
       }

       memcpy(map, cMap, sizeof(cMap));
}

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

---

4. 다시 어항을 바닥에 일렬로 놓아야 한다. 

• 가장 왼쪽에 있는 어항부터

• 아래에 있는 어항부터 가장 위에 있는 어항까지 

• 순서대로 바닥에 놓아야 한다.

 

그림에서 보여준대로 방향으로 for문으로 탐색하면서

map[][] != 0 인 곳을 찾아서 queue에 저장하고 비워준다.

즉, 물고기가 존재하는 곳들만 모은 후 map[N][i]에 배치해준다.

void sortFish()
{
       queue<int> que;
       for (int y = 1; y <= N; y++)
       {
              // 비어있는 열(col)인 경우 skip
              if (map[N][y] == EMPTY) continue;

              for (int x = N; x >= 1; --x)
              {
                     // 중간에 비어져 있다면 break
                     if (map[x][y] == EMPTY)
                           break;

                     // vector에 순서대로 저장해주고 map[][]에서 비워준다.
                     que.push(map[x][y]);
                     map[x][y] = EMPTY;
              }
       }

       int col = 1;
       while (!que.empty())
       {
              map[N][col++] = que.front();
              que.pop();
       }
}

---

5. 가운데를 중심으로 왼쪽 N/2개를 공중 부양시켜 

    전체를 시계 방향으로 180도 회전 시킨 다음, 

    오른쪽 N/2개의 위에 놓아야 한다. 

• 이 작업은 두 번 반복해야한다. 

• 두 번 반복하면 바닥에 있는 어항의 수는 N/4개가 된다.

이전 단계가 끝난 후에는 N개의 어향들이 map[N][]에 있다.

현재 단계까지 수행한다면 아래쪽에 있는 어항은 N/4 이 되는데

처음 입력받을 「N」 을 「4N」 으로 거장해본다면

→ 1    2    3    …     4N-1    4N

 

아래와 같은 규칙을 확인할 수 있다.

3N    3N-1    …    2N+1

N+1    N+2    …    2N

N     N-1    …    1

3N+1    3N+2    …    4N　

• 행(row) 변화 [N-1] → [N-2] → [N-3]

• 각 행의 col 의 길이는 N / 4 동일하다.

• 시작 위치과 방향이 다르므로 이를 Lookup Table로 구성하여 처리

📌 시간 성능 향상을 위한 코드 최적화 (C/C++)

void fold()
{
       int quarterN = N / 4;
       int sCol[4] = {0, N,  N - quarterN + 1, N};
       int cDir[4] = {0, -1, 1, -1};
       
       int srcY = 1;
       for (int i = 1; i <= 3; ++i)
       {
              int col = sCol[i];
              for (int j = 0; j < quarterN; ++j)
              {
                     map[N - i][col] = map[N][srcY];
                     map[N][srcY] = EMPTY;
                     col += cDir[i]; // 해당 row 진행 방향으로
                     srcY++; // 옮겨지는 대상
              }
       }
}

[알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++)

---

6. 다시 물고기 조절 작업 수행

→ 3번 Logic과 동일하므로 설명 생략

 

7. 다시 바닥에 일렬로 놓는 작업 수행

→ 4번 Logic과 동일하므로 설명 생략

---

 8. 물고기가 가장 많은 어항과 가장 적은 어항의

    물고기 수 차이가 K 이하인지 확인

int getDiff()
{
       int maxVal = MIN;
       int minVal = MAX;
       for (int x = 1; x <= N; x++)
       {
              for (int y = 1; y <= N; y++)
              {
                     if (map[x][y] == EMPTY)
                           continue;

                     maxVal = max(maxVal, map[x][y]);
                     minVal = min(minVal, map[x][y]);
              }
       }
       return (maxVal - minVal);
}

어항 안에 있는 가장 많은 물고기와 적은 물고기 수를 구해야 하므로

최대값과 최소값의 차이를 반환해준다.

---

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;

#define MIN 0
#define MAX 2e9
#define EMPTY 0

struct Node
{
	int x, y;
};

inline int min(int& A, int& B) { return A < B ? A : B; }
inline int max(int& A, int& B) { return A > B ? A : B; }
const int dx[] = { 0, 0, -1, 1 };
const int dy[] = { 1, -1, 0, 0 };

const int MAX_N = 100 + 5;
int N, K, ans;
int map[MAX_N][MAX_N];

void input()
{
	scanf("%d %d", &N, &K);

	// 가장 왼쪽에 있는 어항부터 물고기 수 입력
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &map[N][i]);
	}
}

void addFish()
{
	vector<Node> vec;
	int minVal = MAX;
	for (int x = 1; x <= N; x++)
	{
		for (int y = 1; y <= N; y++)
		{
			if (map[x][y] == EMPTY)
				continue;

			// 최소값에 해당하는 어항 찾기
			if (map[x][y] < minVal)
			{
				minVal = map[x][y];
				vec.clear();
				vec.push_back({ x, y });
			}

			// 같은 최소값을 가지고 있는 어항인 경우
			else if (map[x][y] == minVal)
			{
				vec.push_back({ x, y });
			}
		}
	}

	for (int i = 0; i < vec.size(); ++i)
	{
		map[vec[i].x][vec[i].y]++;
	}
}

void roll()
{
	int pivot, w, h;
	pivot = w = h = 1;

	for (int idx = 0; ; ++idx)
	{
		if (pivot - 1 + w + h > N)
			break;

		for (int c = pivot; c < pivot + w; c++)
		{
			for (int r = N; r > N - h; r--)
			{
				int nextR = (N - w) + (c - pivot);
				int nextC = (pivot + w) + (N - r);

				map[nextR][nextC] = map[r][c];
				map[r][c] = EMPTY;
			}
		}

		pivot += (idx / 2 + 1);
		idx % 2 ? w++ : h++;
	}
}

void controlFish()
{
	int cMap[MAX_N][MAX_N] = { 0 };

	for (int x = 1; x <= N; x++)
	{
		for (int y = 1; y <= N; y++)
		{
			if (map[x][y] != EMPTY)
			{
				cMap[x][y] += map[x][y];

				for (int d = 0; d < 4; d++)
				{
					int nextX = x + dx[d];
					int nextY = y + dy[d];

					if (map[nextX][nextY] == EMPTY)
						continue;

					// 물고기가 많은 경우
					if (map[x][y] > map[nextX][nextY]) 
					{
						int diff = (map[x][y] - map[nextX][nextY]) / 5;
						cMap[x][y] -= diff;
						cMap[nextX][nextY] += diff;
					}
				}
			}
		}
	}

	memcpy(map, cMap, sizeof(cMap));
}

void sortFish()
{
	queue<int> que;
	for (int y = 1; y <= N; y++)
	{
		// 비어있는 열(col)인 경우 skip
		if (map[N][y] == EMPTY) continue;

		for (int x = N; x >= 1; --x)
		{
			// 중간에 비어져 있다면 break
			if (map[x][y] == EMPTY)
				break;

			// vector에 순서대로 저장해주고 map[][]에서 비워준다.
			que.push(map[x][y]);
			map[x][y] = EMPTY;
		}
	}

	int col = 1;
	while (!que.empty())
	{
		map[N][col++] = que.front();
		que.pop();
	}
}

void fold()
{
	int quarterN = N / 4;
	int sCol[4] = {0, N,  N - quarterN + 1, N};
	int cDir[4] = {0, -1, 1, -1};
	
	int srcY = 1;
	for (int i = 1; i <= 3; ++i)
	{
		int col = sCol[i];
		for (int j = 0; j < quarterN; ++j)
		{
			map[N - i][col] = map[N][srcY];
			map[N][srcY] = EMPTY;

			col += cDir[i]; // 해당 row 진행 방향으로
			srcY++;	// 옮겨지는 대상
		}
	}
}

int getDiff()
{
	int maxVal = MIN;
	int minVal = MAX;

	for (int x = 1; x <= N; x++)
	{
		for (int y = 1; y <= N; y++)
		{
			if (map[x][y] == EMPTY)
				continue;

			maxVal = max(maxVal, map[x][y]);
			minVal = min(minVal, map[x][y]);
		}
	}

	return (maxVal - minVal);
}

int main()
{
	// freopen("input.txt", "r", stdin);
	input();
	while (1)
	{
		addFish();           // 1. 물고기 추가

		roll();              // 2. 어항 쌓기
		controlFish();       // 3. 물고기 수 조절
		sortFish();          // 4. 물고기 정렬

		fold();              // 5. 어항 접기
		controlFish();       // 6. 물고기 수 조절
		sortFish();          // 7. 물고기 정렬

		ans++;               // 8. 정리 횟수
		if (getDiff() <= K) break;
	}
	printf("%d\n", ans);
}

---

📌 함께 보면 좋은 포스팅

• 삼성 SW 기출 모음

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

• 시간 성능 향상을 위한 코드 최적화 (C/C++)

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

• 행렬 90° 회전