BOJ 23291 - 어항 정리(Java)

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

23291번: 어항 정리

 

풀이

물고기 수의 최대/최소인 어항의 차이가 K이하일 때 까지 반복

 

1. 물고기가 최소인 어항에 물고기 추가

    - 어항에 물고기 수가 최소인 어항들에 물고기 수를 1씩 추가

2. 어항 쌓기

   - 시계 방향 90도로 어항을 말아서 쌓음 

   - 처음에는 가장 왼쪽의 1개 항만 이동, 이후부터는 쌓여져있는 모든 어항을 이동

3. 물고기 수 조절

   - 상하좌우 인접 어항을 확인, 현재 어항이 인접한 어항의 물고기 수와 비교

   - (현재 어항 - 이동할 어항)/5 >0 이라면 물고기 이동(물고기 이동은 모든 어항에서 동시에 발생)

4. 어항 일렬로 배치

    - 쌓여진 어항을 일렬로 재배치

    - 가장 왼쪽에 있는 어항부터 밑에서 위의 순서로 배치

5. 어항 접기

    - 2번 반복

    - 가운데를 중심으로 왼쪽을 180도 회전시켜 오른쪽 위에 배치

6. 물고기 수 조절

7. 어항 일렬로 배치 

 

 

어항 쌓기

private static void make2D() {
	int pivotX = 1;
	int w = 1;
	int h = 1;
	int idx = 0;
	while (pivotX - 1 + w + h <= N) {
		idx++;
		for (int x = pivotX; x < pivotX + w; x++) {
			for (int y = N; y > N - h; y--) {
				int ny = N - w + x - pivotX;
				int nx = pivotX + w + N - y;
				map[ny][nx] = map[y][x];
				map[y][x] = 0;
			}
		}
		pivotX += w;
		if (idx % 2 == 0) {
			w++;
		} else {
			h++;
		}
	}
}

 

물고기 조절

물고기의 이동은 동시에 진행되기 때문에 물고기의 이동을 저장하기 위한 배열 생성

물고기가 존재하는 위치마다 상하좌우의 어항을 확인하여 물고기가 있다면 물고기 이동 조건에 해당하는 지 확인, 이동 수를 배열에 누적 갱신

물고기 이동 배열을 완전히 갱신한 후에 배열의 각 요소를 이동수만큼 ± 계산

private static void adjustFish() {
	int[][] adjustMap = new int[N + 1][N + 1];

	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			if (map[y][x] == 0)
				continue;
			for (int d = 0; d < 4; d++) {
				int ny = y + dy[d];
				int nx = x + dx[d];
				if ((ny < 1 || nx < 1 || ny > N || nx > N) || map[ny][nx] == 0)
					continue;
				int diff = map[y][x] - map[ny][nx];
				diff /= 5;
				if (diff > 0) {
					adjustMap[y][x] -= diff;
					adjustMap[ny][nx] += diff;
				}
			}
		}
	}
	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			map[y][x] += adjustMap[y][x];
		}
	}
}

 

 

어항 일렬 배치

private static void make1D() {
	List<Integer> list = new ArrayList<>();
	for (int x = 1; x <= N; x++) {
		for (int y = N; y >= 1; y--) {
			if (map[y][x] == 0)
				break;
			list.add(map[y][x]);
			map[y][x] = 0;
		}
	}
	for (int i = 0; i < N; i++) {
		map[N][i + 1] = list.get(i);
	}
}

 

어항 접기

접기는 2번 반복 N -> N/2 -> N/4

private static void fold() {
	List<Integer> list =new ArrayList<>();
	int pivotX = 1;
	int yCnt = 1;
	for (int cnt = 1; cnt <= 2; cnt++) {
		int _y= N - yCnt * 2 + 1;
		for (int y = N; y > N-yCnt; y--) {
			list.clear();
			for (int x = pivotX; x < pivotX +(N - pivotX + 1) / 2; x++) {
				list.add(map[y][x]);
				map[y][x]=0;
			}
			for(int idx=0;idx<list.size();idx++) {
				map[_y][N-idx]=list.get(idx);
			}
			_y++;
		}
		yCnt *= 2;
		pivotX += N / 2;
	}
}

 

 

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {
	static final int INF = 987654321;
	static int N, K;
	static int[][] map;
	static int[] dy = { 0, 1, 0, -1 };
	static int[] dx = { 1, 0, -1, 0 };

	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		map = new int[N + 1][N + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			map[N][i] = Integer.parseInt(st.nextToken());
		}

		int time = 0;
		while (!isFinish()) {
			time++;
			pushFish(); 
			
			make2D();
			adjustFish();
			
			make1D();
			fold();
			adjustFish();
			
			make1D();
		}
		System.out.println(time);
	}

	private static boolean isFinish() {
		int max = 0;
		int min = INF;
		for (int y = 1; y <= N; y++) {
			for (int x = 1; x <= N; x++) {
				if (map[y][x] == 0)
					continue;
				if (max < map[y][x])
					max = map[y][x];
				if (min > map[y][x])
					min = map[y][x];
			}
		}
		if (max - min <= K) {
			return true;
		} else
			return false;
	}

	private static void fold() {
		// 2번 반복
		List<Integer> list =new ArrayList<>();
		int pivotX = 1;
		int yCnt = 1;
		for (int cnt = 1; cnt <= 2; cnt++) {
			int _y=N-yCnt*2+1;
			for (int y = N; y > N-yCnt; y--) {
				
				list.clear();
				for (int x = pivotX; x < pivotX +(N - pivotX + 1) / 2; x++) {
					list.add(map[y][x]);
					map[y][x]=0;
				}
				for(int idx=0;idx<list.size();idx++) {
					map[_y][N-idx]=list.get(idx);
				}
				_y++;
			}
			yCnt *= 2;
			pivotX += N / 2;
		}

	}

	private static void make1D() {
		List<Integer> list = new ArrayList<>();
		for (int x = 1; x <= N; x++) {
			for (int y = N; y >= 1; y--) {
				if (map[y][x] == 0)
					break;
				list.add(map[y][x]);
				map[y][x] = 0;
			}
		}
		for (int i = 0; i < N; i++) {
			map[N][i + 1] = list.get(i);
		}
	}

	private static void make2D() {
		int pivotX = 1;
		int w = 1;
		int h = 1;
		int idx = 0;
		while (pivotX - 1 + w + h <= N) {
			idx++;
			for (int x = pivotX; x < pivotX + w; x++) {
				for (int y = N; y > N - h; y--) {
					int ny = N - w + x - pivotX;
					int nx = pivotX + w + N - y;
					map[ny][nx] = map[y][x];
					map[y][x] = 0;
				}
			}
			pivotX += w;
			if (idx % 2 == 0) {
				w++;
			} else {
				h++;
			}
		}
	}

	// 물고기 수가 가장 적은 어항에 물고기 추가
	private static void pushFish() {
		List<Integer> posList = new ArrayList<>();
		int min = INF;
		for (int i = 1; i <= N; i++) {
			if (map[N][i] < min) {
				min = map[N][i];
				posList.clear();
				posList.add(i);
			} else if (map[N][i] == min) {
				posList.add(i);
			}
		}

		for (int idx : posList) {
			map[N][idx]++;
		}
	}

	private static void adjustFish() {
		int[][] adjustMap = new int[N + 1][N + 1];

		for (int y = 1; y <= N; y++) {
			for (int x = 1; x <= N; x++) {
				if (map[y][x] == 0)
					continue;
				for (int d = 0; d < 4; d++) {
					int ny = y + dy[d];
					int nx = x + dx[d];
					if ((ny < 1 || nx < 1 || ny > N || nx > N) || map[ny][nx] == 0)
						continue;
					int diff = map[y][x] - map[ny][nx];
					diff /= 5;
					// 현재 위치에서 다음 위치로 물고기 보내기 가능
					if (diff > 0) {
						adjustMap[y][x] -= diff;
						adjustMap[ny][nx] += diff;
					}
				}
			}
		}
		// 보내고 받는 물고기 수를 +- 계산
		for (int y = 1; y <= N; y++) {
			for (int x = 1; x <= N; x++) {
				map[y][x] += adjustMap[y][x];
			}
		}
	}

}