[BOJ][Java] 백준 23291번: 어항 정리

문제 설명

마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바닥 위에 놓여져 있다. 어항에는 물고기가 한 마리 이상 들어있다. <그림 1>은 어항 8개가 바닥 위에 놓여있는 상태이며, 칸에 적힌 값은 그 어항에 들어있는 물고기의 수이다. 편의상 어항은 정사각형으로 표현했다.

<그림 1>

어항을 한 번 정리하는 과정은 다음과 같이 이루어져 있다.

먼저, 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다. 만약, 그러한 어항이 여러개라면 물고기의 수가 최소인 어항 모두에 한 마리씩 넣는다. 위의 예시의 경우 물고기의 수가 가장 적은 어항에는 물고기가 2마리 있고, 그러한 어항은 2개가 있다. 따라서, 2개의 어항에 물고기를 한 마리씩 넣어 <그림 2>와 같아진다.

<그림 2>

이제 어항을 쌓는다. 먼저, 가장 왼쪽에 있는 어항을 그 어항의 오른쪽에 있는 어항의 위에 올려 놓아 <그림 3>이 된다.

<그림 3>

이제, 2개 이상 쌓여있는 어항을 모두 공중 부양시킨 다음, 전체를 시계방향으로 90도 회전시킨다. 이후 공중 부양시킨 어항을 바닥에 있는 어항의 위에 올려놓는다. 바닥의 가장 왼쪽에 있는 어항 위에 공중 부양시킨 어항 중 가장 왼쪽에 있는 어항이 있어야 한다. 이 작업은 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 있을때까지 반복한다.

먼저, <그림 4>와 같이 어항이 놓인 상태가 변하고, 한 번 더 변해서 <그림 5>가 된다.

<그림 4>

<그림 5>

<그림 5>에서 한 번 더 어항을 공중 부양시키는 것은 불가능하다. 그 이유는 <그림 6>과 같이 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 없기 때문이다.

<그림 6>

공중 부양 작업이 모두 끝나면, 어항에 있는 물고기의 수를 조절한다.

모든 인접한 두 어항에 대해서, 물고기 수의 차이를 구한다. 이 차이를 5로 나눈 몫을 d라고 하자. d가 0보다 크면, 두 어항 중 물고기의 수가 많은 곳에 있는 물고기 d 마리를 적은 곳에 있는 곳으로 보낸다. 이 과정은 모든 인접한 칸에 대해서 동시에 발생한다. 이 과정이 완료되면 <그림 7>이 된다.

<그림 7>

이제 다시 어항을 바닥에 일렬로 놓아야 한다. 가장 왼쪽에 있는 어항부터, 그리고 아래에 있는 어항부터 가장 위에 있는 어항까지 순서대로 바닥에 놓아야 한다. <그림 8>이 바닥에 다시 일렬로 놓은 상태이다.

<그림 8>

다시 공중 부양 작업을 해야 한다. 이번에는 가운데를 중심으로 왼쪽 N/2개를 공중 부양시켜 전체를 시계 방향으로 180도 회전 시킨 다음, 오른쪽 N/2개의 위에 놓아야 한다. 이 작업은 두 번 반복해야한다. 두 번 반복하면 바닥에 있는 어항의 수는 N/4개가 된다. <그림 9>는 이 작업을 1번 했을 때, <그림 10>은 다시 한 번 더 했을 때이다.

<그림 9>

<그림 10>

여기서 다시 위에서 한 물고기 조절 작업을 수행하고, 바닥에 일렬로 놓는 작업을 수행한다. <그림 10>에서 조절 작업을 마친 결과는 <그림 11>이 되고, 여기서 다시 바닥에 일렬로 놓는 작업을 수행하면 <그림 12>가 된다.

<그림 11>

<그림 12>

어항의 수 N, 각 어항에 들어있는 물고기의 수가 주어진다. 물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 되려면 어항을 몇 번 정리해야하는지 구해보자.

 

문제 풀이

 

 

풀이 코드

<배열로 구현>

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

public class BOJ23291 {
    private static int[][] block;
    private static int N, K;

    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());
        block = new int[N+1][N+1];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) block[0][i] = Integer.parseInt(st.nextToken());

        int ans = 0;

        while (!isSuccess()){
            blockProcess();
            ans += 1;
        }

        System.out.println(ans);
    }

    private static boolean isSuccess() {
        int max=Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(block[i][j] == 0) continue;
                max = Math.max(max, block[i][j]);
                min = Math.min(min, block[i][j]);
            }
        }
        return max - min <= K;
    }

    private static void blockProcess() {
        push2Min();
        rotateBlocks();
        adjustBlocks();
        arrangeBlocks();
        foldBlocks();
        adjustBlocks();
        arrangeBlocks();
    }

    private static void push2Min() {
        int min = Integer.MAX_VALUE;
        for(int i=0; i<N; i++) min = Math.min(min, block[0][i]);
        for(int i=0; i<N; i++) if(block[0][i] == min) block[0][i]+=1;
    }

    private static void rotateBlocks() {
        int width=1, height=1, start = 1; //start: N줄의 처음 시작 위치
        int index = 0; //짝수일 때는 width가 늘어나고, 홀수일 땐 height가 늘어남

        while(start + height - 1  < N){
            index+=1;
            for(int y=0; y<height; y++){
                for(int x=start-width; x<start; x++){
                    block[start-x][start+y] = block[y][x];
                    block[y][x] = 0;
                }
            }
            start+=height;

            if(index%2==0) width+=1;
            else height+=1;
        }
    }

    private static void adjustBlocks() {
        int[][] temp = new int[N][N];
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                calcDiff(temp, i, j, i+1, j);
                calcDiff(temp, i, j, i, j+1);
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                block[i][j] += temp[i][j];
            }
        }
    }

    private static void arrangeBlocks() {
        int[] temp = new int[N];
        int idx = 0;

        for(int x =0; x<N; x++){
            for(int y=0; y<N; y++){
                if(block[y][x] != 0){
                    temp[idx++] = block[y][x];
                    block[y][x] = 0;
                }
            }
        }

        for(int i=0; i<N; i++) block[0][i] = temp[i];
    }

    private static void foldBlocks() {

        for(int i=0; i<N/4; i++){
            block[1][N-1-i] = block[0][i];
            block[0][i] = 0;
        }

        for(int i=0; i<N/4; i++){
            block[2][N/4*3+i] = block[0][N/4+i];
            block[0][N/4+i] = 0;
        }

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

    private static void calcDiff(int[][] temp, int n1, int p1, int n2, int p2){
        if(block[n1][p1] == 0) return;
        if(block[n2][p2] == 0) return;

        int value = Math.abs(block[n1][p1] - block[n2][p2])/5;
        if(block[n1][p1] > block[n2][p2]){
            temp[n1][p1] -= value;
            temp[n2][p2] += value;
        }else{
            temp[n2][p2] -= value;
            temp[n1][p1] += value;
        }
    }
}

<리스트로 구현>

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

public class Main {
    private static ArrayList<ArrayList<Integer>> blockList = new ArrayList<>();
    private static int N, K;
    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());
        initList(blockList);

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) blockList.get(N-1).add(Integer.parseInt(st.nextToken()));

        int ans = 0;
        while (!isSuccess()){
            blockProcess();
            ans += 1;
        }

        System.out.println(ans);
    }

    private static void blockProcess() {
        addOne2Min();
        rotateBlocks();
        adjustFish();
        arrangeFish();
        foldBlocks();
        adjustFish();
        arrangeFish();
    }

    private static boolean isSuccess(){
        return Collections.max(blockList.get(N-1)) - Collections.min(blockList.get(N-1)) <= K;
    }

    private static void addOne2Min() {
        int min = Collections.min(blockList.get(N-1));
        for (int i = 0; i < blockList.get(N-1).size(); i++)
            if (blockList.get(N-1).get(i) == min) blockList.get(N-1).set(i, min + 1);
    }

    private static void rotateBlocks() {
        int width = 1, height = 1;

        for(int index=0; ; index++){
            if (blockList.get(N-1).size() - width < height) break;

            for(int y =1; y<=height; y++){
                for(int x = width; x>=1; x--){
                    blockList.get(N-x-1).add(blockList.get(N-y).remove(0));
                }
            }

            if(index % 2 == 0) height+=1;
            else width+=1;
        }
    }

    private static void adjustFish() {
        Queue<int[]> queue = new LinkedList<>();

        for(int i = 0; i< N; i++){
            for(int j=0; j<blockList.get(i).size(); j++){
                calcDiff(queue, i, j, i, j+1);
                calcDiff(queue, i, j, i+1, j);
            }
        }

        while(!queue.isEmpty()){
            int[] pos = queue.poll();
            blockList.get(pos[0]).set(pos[1], blockList.get(pos[0]).get(pos[1])-pos[4]);
            blockList.get(pos[2]).set(pos[3], blockList.get(pos[2]).get(pos[3])+pos[4]);
        }
    }

    private static void calcDiff(Queue<int[]> queue, int n1, int p1, int n2, int p2){
        try{
            int value = Math.abs(blockList.get(n1).get(p1) - blockList.get(n2).get(p2))/5;
            if(blockList.get(n1).get(p1) > blockList.get(n2).get(p2)){
                queue.add(new int[]{n1, p1, n2, p2, value});
            }else{
                queue.add(new int[]{n2, p2, n1, p1, value});
            }
        }catch (IndexOutOfBoundsException ignored){}
    }

    private static void arrangeFish() {
        ArrayList<Integer> temp = new ArrayList<>();

        for(int i=0; i < N; i++){
            for(int j = N-1; j>=0; j--){
                if(blockList.get(j).size() != 0)
                    temp.add(blockList.get(j).remove(0));
            }
        }

        for(int t : temp) blockList.get(N-1).add(t);
    }

    private static void foldBlocks() {
        for(int i=0; i<N/2; i++)
            blockList.get(N-2).add(blockList.get(N-1).remove(0));
        Collections.reverse(blockList.get(N - 2));

        for(int i=0; i<2; i++){
            for(int j=0; j<N/4; j++){
                blockList.get(N-4+i).add(blockList.get(N-i-1).remove(0));
            }
            Collections.reverse(blockList.get(N - 4+ i));
        }
    }

    private static void initList(ArrayList<ArrayList<Integer>> list) {
        for (int i = 0; i < N; i++) list.add(new ArrayList<>());
    }
}

 

<출처>

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

23291번: 어항 정리