BOJ 23291 : 어항 정리 (삼성 SW TEST A형)

www.acmicpc.net/workbook/view/1152 (A형 문제집)

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

어항은 N x N 배열의 row = N 부터 채워나간다.

#define MAX (100 + 10)

int N, K;
int FISH[MAX][MAX];

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

	for (int i = 1; i <= N; i++)
	{
		int f;

		scanf("%d", &f);
		FISH[N][i] = f;
	}
}

main은 아래와 같이 구성된다.

addFish() - 가장 적은 어항에 물고기 추가

move() - 가능한 만큼 어항 쌓기

spreadFish() - 물고기의 이동

fishSort() - 어항 재정리

fold() - 어항 2번 접기

spreadFish() - 물고기의 이동

fishSort() - 어항 재정리

count++ - 어항 정리 횟수 증가

check() - 어항의 물고기 수 차이 K 이하 check

int main(void)
{
	input();

	int count = 0;

	while (1)
	{
		addFish();
		move();
		spreadFish();
		fishSort();
		fold();
		spreadFish();
		fishSort();
		count++;
        
		if (check()) break;
	}

	printf("%d\n", count);

	return 0;
}

addFish() - 가장 적은 어항에 물고기 추가

가장 작은 물고기의 수를 먼저 찾고, 그 물고기의 수인 곳에 물고기를 더한다.

void addFish()
{
	int min = 0x7fff0000;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (FISH[r][c] == 0) continue;
			if (FISH[r][c] < min) min = FISH[r][c];
		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			if (FISH[r][c] == min) FISH[r][c]++;

}

move() - 가능한 만큼 어항 쌓기

어항이 움직이는 곳을 start, 그리고 start 지점에서 width / height 만큼 움직인다고 하자.

그림을 그려가면서 start, width, height를 구해보면 아래와 같다.

1, 1, 1
2, 1, 2
3, 2, 2
5, 2, 3
7, 3, 3
10, 3, 4

그리고 start + width + height - 1이 N보다 커지는 시점에서 어항 쌓기가 종료된다.

i = 0부터 시작하여 i가 홀수인 경우에는 width를 증가, 짝수면 heigth를 증가하고,

start는 (i / 2 + 1)을 누적하면 1, 2, 3, 5, 7, 10, ... 의 결과가 나온다.

변경되는 어항의 좌표 (nr, nc) width, start, height로 시계방향으로 돌리면 된다.

void move()
{
	int start, width, height;

	start = width = height = 1;

	int i = 0;
	while (1)
	{
		if (start + width + height - 1 > N) break;

		for (int c = start; c < start + width; c++)
		{
			for (int r = N; r > N - height; r--)
			{
				int nr, nc;

				nr = N - width + c - start;
				nc = start + width + N - r;

				FISH[nr][nc] = FISH[r][c];
				FISH[r][c] = 0;
			}
		}

		if (i % 2) width++;
		else height++;

		start += (i / 2 + 1);

		i++;
	}
}

spreadFish() - 물고기의 이동

물고기가 있는 칸만 검사하기에는 어항이 매우 불규칙적이다.

따라서 모든 N x N 배열을 검사하면 된다.

물고기가 0인 경우를 벽으로 생각하여 온풍기 안녕!의 controlTemperature()의 로직을 참고하여 구현한다.

/* 순서대로 오른쪽 : 1, 왼쪽 : 2, 위 : 3, 아래 : 4 */
int dr[] = { 0, 0, 0, -1, 1 };
int dc[] = { 0, 1, -1, 0, 0 };

void spreadFish()
{
	int tmpFISH[MAX][MAX] = { 0 };

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (FISH[r][c] > 0)
			{
				int save = FISH[r][c];

				for (int dir = 1; dir <= 4; dir++)
				{
					int nr, nc;

					nr = r + dr[dir];
					nc = c + dc[dir];

					if (FISH[nr][nc] == 0) continue;

					if (FISH[r][c] > FISH[nr][nc]) // 물고기가 많은 경우만 이동
					{
						int diff = (FISH[r][c] - FISH[nr][nc]) / 5;

						save -= diff;
						tmpFISH[nr][nc] += diff;
					}
				}

				tmpFISH[r][c] += save;
			}

		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			FISH[r][c] = tmpFISH[r][c];
}

fishSort() - 어항 재정리

어항을 다시 정리한다. row = N부터 오른쪽으로 이동하여 물고기가 있는 경우, 위로 간다.

위로 가다가 다시 물고기가 0인 곳을 만나면 row = N으로 변경하여 위로 가면 된다.

이 로직은 어항을 접은 후에도 마찬가지로 적용된다.

void fishSort()
{
	int idx;
	int tmpFISH[MAX][MAX] = { 0 };

	idx = 1;
	for (int c = 1; c <= N; c++)
	{
		if (FISH[N][c] == 0) continue;

		int row = N;
		while (1)
		{
			if (FISH[row][c] == 0) break;

			tmpFISH[N][idx++] = FISH[row][c];
			row--;
		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			FISH[r][c] = tmpFISH[r][c];
}

fold() - 어항 2번 접기

크기만 N으로 다를 뿐, 좌표 변환은 N에 대해서 변경되므로 아래와 같이 구현한다.

void fold()
{
	int sc = N / 2 + 1;
	for (int c = N / 2; c >= 1; c--) FISH[N - 1][sc++] = FISH[N][c];
	for (int c = N / 2; c >= 1; c--) FISH[N][c] = 0;

	for (int r = N - 1; r <= N; r++)
	{
		int ec = N / 4 * 3;
		int fix = N;
		for (int c = N / 2 + 1; c <= ec; c++)
		{
			int nr, nc;

			nr = 2 * N - r - 3;
			nc = fix--;

			FISH[nr][nc] = FISH[r][c];
			FISH[r][c] = 0;
		}
	}
}

check() - 어항의 물고기 수 차이 K 이하 check

물고기의 차이가 K 이하인지 check하면 된다.

int check()
{
	int max = 0;
	int min = 0x7fff0000;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (FISH[r][c] == 0) continue;
			if (FISH[r][c] < min) min = FISH[r][c];
			if (FISH[r][c] > max) max = FISH[r][c];
		}
	}

	if (max - min <= K) return 1;
	return 0;
}

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (100 + 10)

int N, K;
int FISH[MAX][MAX];

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

	for (int i = 1; i <= N; i++)
	{
		int f;

		scanf("%d", &f);
		FISH[N][i] = f;
	}
}

void output(int n)
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%2d ", FISH[r][c]);
		putchar('\n');
	}

	putchar('\n');
}

void addFish()
{
	int min = 0x7fff0000;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (FISH[r][c] == 0) continue;
			if (FISH[r][c] < min) min = FISH[r][c];
		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			if (FISH[r][c] == min) FISH[r][c]++;

}

void move()
{
	int start, width, height;

	start = width = height = 1;

	int i = 0;
	while (1)
	{
		if (start + width + height - 1 > N) break;

		for (int c = start; c < start + width; c++)
		{
			for (int r = N; r > N - height; r--)
			{
				int nr, nc;

				nr = N - width + c - start;
				nc = start + width + N - r;

				FISH[nr][nc] = FISH[r][c];
				FISH[r][c] = 0;
			}
		}

		if (i % 2) width++;
		else height++;

		start += (i / 2 + 1);

		i++;
	}
}

/* 순서대로 오른쪽 : 1, 왼쪽 : 2, 위 : 3, 아래 : 4 */
int dr[] = { 0, 0, 0, -1, 1 };
int dc[] = { 0, 1, -1, 0, 0 };

void spreadFish()
{
	int tmpFISH[MAX][MAX] = { 0 };

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (FISH[r][c] > 0)
			{
				int save = FISH[r][c];

				for (int dir = 1; dir <= 4; dir++)
				{
					int nr, nc;

					nr = r + dr[dir];
					nc = c + dc[dir];

					if (FISH[nr][nc] == 0) continue;

					if (FISH[r][c] > FISH[nr][nc]) // 물고기가 많은 경우만 이동
					{
						int diff = (FISH[r][c] - FISH[nr][nc]) / 5;

						save -= diff;
						tmpFISH[nr][nc] += diff;
					}
				}

				tmpFISH[r][c] += save;
			}

		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			FISH[r][c] = tmpFISH[r][c];
}

void fishSort()
{
	int idx;
	int tmpFISH[MAX][MAX] = { 0 };

	idx = 1;
	for (int c = 1; c <= N; c++)
	{
		if (FISH[N][c] == 0) continue;

		int row = N;
		while (1)
		{
			if (FISH[row][c] == 0) break;

			tmpFISH[N][idx++] = FISH[row][c];
			row--;
		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			FISH[r][c] = tmpFISH[r][c];
}

void fold()
{
	int sc = N / 2 + 1;
	for (int c = N / 2; c >= 1; c--) FISH[N - 1][sc++] = FISH[N][c];
	for (int c = N / 2; c >= 1; c--) FISH[N][c] = 0;

	for (int r = N - 1; r <= N; r++)
	{
		int ec = N / 4 * 3;
		int fix = N;
		for (int c = N / 2 + 1; c <= ec; c++)
		{
			int nr, nc;

			nr = 2 * N - r - 3;
			nc = fix--;

			FISH[nr][nc] = FISH[r][c];
			FISH[r][c] = 0;
		}
	}
}

int check()
{
	int max = 0;
	int min = 0x7fff0000;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (FISH[r][c] == 0) continue;
			if (FISH[r][c] < min) min = FISH[r][c];
			if (FISH[r][c] > max) max = FISH[r][c];
		}
	}

	if (max - min <= K) return 1;
	return 0;
}

int main(void)
{
	input();

	int count = 0;

	while (1)
	{
		addFish();
		move();
		spreadFish();
		fishSort();
		fold();
		spreadFish();
		fishSort();
		count++;

		if (check()) break;
	}

	printf("%d\n", count);

	return 0;
}

실제 A형에서는 FISH 배열을 잘 초기화 하자.

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

BOJ 23290 : 마법사 상어와 복제 (삼성 SW TEST A형) (0)	2021.11.06
BOJ 23289 : 온풍기 안녕! (삼성 SW TEST A형) (0)	2021.11.06
BOJ 23288 : 주사위 굴리기 2 (삼성 SW TEST A형) (0)	2021.10.25
BOJ 21611 : 마법사 상어와 블리자드 (삼성 SW TEST A형) (0)	2021.05.01
BOJ 21610 : 마법사 상어와 비바라기 (삼성 SW TEST A형) (0)	2021.04.30

피로물든딸기의 라이브러리

BOJ 23291 : 어항 정리 (삼성 SW TEST A형)

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

댓글

티스토리툴바

BOJ 23291 : 어항 정리 (삼성 SW TEST A형)

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

관련글

댓글

티스토리툴바