[백준] 23291번: 어항 정리

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

23291번: 어항 정리

문제 이해

처음에 풀고 다 맞는데 왜 틀리지!!!!

이러고 포기했다가 새로운 방식을 접하고 다시 풀었다.

좌표 계산이 아주 더러웠던 문제이다

 

처음에 어항이 공중부양하는 그 파트만 잘 처리하면 나머지는 무난하게 처리할 수 있다.

수를 조절하는 부분은 그냥 BFS를 돌리면서 값 비교하고, 표에 증감표시를 해두었다가 마지막에 적용하면 된다.

4번 접는 부분은 그냥 좌표 계산해서 0행부터 4행까지 붙여 넣기만 하면 된다.

 

그래서 공중부양하는 파트만 설명을 남겨본다.

Fold_Bowls()

처음에 N행에 저걸 두고 배열 복붙을 하려고 하니 좌표로 꼬여서 2시간이 걸렷지만(...) 계산하지 못했다.

그냥 0행에 두고 밑으로 쌓는게 훨!!씬!! 낫다

 

이렇게 그림을 그리면 패턴이 발견된다.

일단 f는 회색 네모를 갖다 붙일 열 번호이다.

w, h는 회색 네모의 너비, 높이이다.

i가 짝수일 때는 h가 늘어나고, i가 홀수일 때는 w가 늘어난다.

f는 h 만큼 늘어나는데, h가 증가하는 경우, 증가하기 전의 h를 더해줘야 하므로 f 증가를 먼저시킨다.

 

그럼 좌표의 이동도 수식화할 수 있다.

가로 세로가 다른 경우를 보기 위해 i==3일 때를 살펴보면 좌표들 간에도 규칙이 있다.

전의 좌표를 (r, c)라고 하면,

변경 후의 x 좌표는 f(6) + r인것을 알 수 있다. 

y좌표가 눈에 확 들어오지 않는데, 6-c이다. 6은 f의 값이다. 즉 y는 f-c라는 것이다.

 

정리하면, 기존 좌표가 (r, c)였다면 새로운 좌표는 (f-c, f+r)이다

 

이걸 코드로 구현하면 어항 공중 부양 작업을 할 수 있다.

void Fold_Bowls(void) {
	int w = 1, h = 1;
	int f = 1;
	for (int i = 0; ; i++) {
		// f위치에 w*h 만큼 갖다 붙일 거임
		if (f + h - 1 >= N) break;
		int r, c;
		for (r = 0; r < h; r++) {
			for (c = f - w; c < f; c++) {
				map[f - c][f + r] = map[r][c];
				map[r][c] = 0;
			}
		}
		f += h;
		if (i % 2 == 0) h++;
		else w++;
	}
}

 

Make_Linear()

접혀져있는 어항 배열을 다시 일렬로 만드는 함수이다.

이렇게 되어있으면 5 4 3 6 1 2 7 8 이렇게 읽어야 한다.

어항은 어떻게 접던지 항상 (0, N-1)에는 어항의 끝이 있다. 그니까 여기서부터 x좌표를 앞으로 당기면서 0이 아닌 원소를 찾는다. (8 -> 7 -> 6 -> 5 로 탐색하다가 0이면 끝낸단 소리)

그 후에 그 시작점 (5)에서 행을 쭉 읽으면 된다. 

void Make_Linear(void) {
	// N-1부터 앞으로 0이 아닐때까지 간다
	int x;
	int cnt = 0;
	memset(tmp, 0, sizeof(tmp));
	for (x = N - 1; x >= 0; x--) {
		if (map[0][x] == 0) {
			x++;
			break;
		}
	}
	for (; x < N; x++) {
		for (int y = 0; y < N; y++) {
			if (map[y][x] == 0) break;
			tmp[0][cnt++] = map[y][x];
		}
	}
	memcpy(map, tmp, sizeof(tmp));
}

 

전체 코드

#include <stdio.h>
#include <string.h>
#define MAXN 100
#define ABS(x) (((x)>0) ? (x): -(x))
int N, K; // 어항 개수, 물고기 수 차이
int size;

int map[MAXN + 5][MAXN + 5];
int tmp[MAXN + 5][MAXN + 5];
int visited[MAXN + 5][MAXN + 5];
int adjust[MAXN + 5][MAXN + 5];
int dy[] = { 0, 0, 1, -1 };
int dx[] = { 1, -1, 0, 0 };

void Get_Input(void) {
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		scanf("%d", &map[0][i]);
	}
}

void Fish_Increase(void) {
	int min = 0x7fffffff;
	for (int i = 0; i < N; i++) {
		if (map[0][i] < min) min = map[0][i];
	}
	for (int i = 0; i < N; i++) {
		if (map[0][i] == min) map[0][i]++;
	}
}

void Fold_Bowls(void) {
	int w = 1, h = 1;
	int f = 1;
	for (int i = 0; ; i++) {
		// f위치에 w*h 만큼 갖다 붙일 거임
		if (f + h - 1 >= N) break;
		int r, c;
		for (r = 0; r < h; r++) {
			for (c = f - w; c < f; c++) {
				map[f - c][f + r] = map[r][c];
				map[r][c] = 0;
			}
		}
		f += h;
		if (i % 2 == 0) h++;
		else w++;
	}
}

typedef struct st {
	int y, x;
}ELE;
ELE q[MAXN * MAXN * 10];
int wp, rp;
void enq(int y, int x) { q[wp].y = y, q[wp++].x = x; }
ELE deq(void) { return q[rp++]; }
int empty(void) { return wp == rp;}

void Adjust_Fish(void) {
	// (0, N-1)엔 항상 뭐가 있음, 여기서 BFS를 하면서 모든 숫자 칸을 살핀다
	wp = rp = 0;
	memset(visited, 0, sizeof(visited));
	memset(adjust, 0, sizeof(adjust));

	enq(0, N-1);
	//visited[0][N - 1] = 1;
	while (!empty()) {
		ELE cur = deq();
		if (visited[cur.y][cur.x] == 1) continue;
		visited[cur.y][cur.x] = 1;
		for (int i = 0; i < 4; i++) {
			int ny = cur.y + dy[i];
			int nx = cur.x + dx[i];
			if (ny < 0 || ny > N || nx < 0 || nx > N) continue;
			if (map[ny][nx] == 0) continue;
			if (visited[ny][nx] == 1) continue;

			int diff = ABS(map[cur.y][cur.x] - map[ny][nx]) / 5;
			if (diff > 0) {
				if (map[cur.y][cur.x] > map[ny][nx]) {
					adjust[cur.y][cur.x] -= diff;
					adjust[ny][nx] += diff;
				}
				else {
					adjust[cur.y][cur.x] += diff;
					adjust[ny][nx] -= diff;
				}
			}
			enq(ny, nx);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (adjust[i][j] != 0) {
				map[i][j] += adjust[i][j];
			}
		}
	}
}

void Make_Linear(void) {
	// N-1부터 앞으로 0이 아닐때까지 간다
	int x;
	int cnt = 0;
	memset(tmp, 0, sizeof(tmp));
	for (x = N - 1; x >= 0; x--) {
		if (map[0][x] == 0) {
			x++;
			break;
		}
	}
	for (; x < N; x++) {
		for (int y = 0; y < N; y++) {
			if (map[y][x] == 0) break;
			tmp[0][cnt++] = map[y][x];
		}
	}
	memcpy(map, tmp, sizeof(tmp));
}

void Fold_Fourth(void) {
	for (int i = 0; i < N / 4; i++) {
		map[1][N - 1 - i] = map[0][i];
		map[0][i] = 0;
	}
	for (int i = 0; i < N / 4; i++) {
		map[2][(N / 4)*3+i] = map[0][N / 4 + i];
		map[0][N / 4 + i] = 0;
	}
	for (int i = 0; i < N / 4; i++) {
		map[3][N - 1 - i] = map[0][(N / 4) * 2 + i];
		map[0][(N / 4) * 2 + i] = 0;
	}
}

int Check(void) {
	int min = 0x7fffffff;
	int max = 0;
	for (int i = 0; i < N; i++) {
		if (map[0][i] < min) min = map[0][i];
		if (map[0][i] > max) max = map[0][i];
	}
	if (max - min <= K) return 1;
	else return 0;
}

int main(void) {
	int t;
	freopen("in.txt", "r", stdin);
	Get_Input();
	for (t = 1; ; t++) {
		Fish_Increase();
		Fold_Bowls();
		Adjust_Fish();
		Make_Linear();
		Fold_Fourth();
		Adjust_Fish();
		Make_Linear();
		if(Check()) break;
	}
	printf("%d", t);
	return 0;
}