[백준 - 25568번] 피라미드 - Java

문제 링크

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

문제

티어: 플래티넘 5
알고리즘: 그리디, 애드 혹

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 1\,000)$ 

두 번째 줄부터 $N$개의 줄에 걸쳐 블록 피라미드의 각 행의 상태가 주어진다. $i + 1$번째 줄에는 블록 피라미드의 $i$행을 이루는 블록 $i$개의 색상 정보가 공백을 사이에 두고 주어진다. 색상 정보는 $0$, $1$ 또는 $2$의 정수이며, 각각 $3$가지의 다른 색상을 표현한다.

출력

피라미드의 맞닿아 있는 블록의 색깔이 같은 경우가 없도록 하기 위한 연산 사용 횟수의 최솟값을 출력하라. 해당 연산만으로 목표를 이루는 것이 불가능하다면 -1을 출력하라.

풀이

연산을 최소한으로 사용해서 올바른 피라미드로 변환해야 한다.

올바른 피라미드가 무엇인지 직접 그리다 보면 결국 두 개의 피라미드 타입만 있다는 것을 알 수있다. 왜냐하면 두 번째 행의 순서가 나머지 행을 결정하기 때문이다.

그리고 잘 관찰하면 다음과 같은 패턴이 있음을 알 수 있다.
0
1 2인 경우

3번째 행은 2 0 1 -> pyramid[1][1] pyramid[0][0] pyramid[1][0]
4번째 행은 0 1 2 0 -> 3번째 행의 2 0 1에서 인덱스 [1][2][0]으로 배치하고 순서대로 4번 사용됨.

이러한 패턴이 반복된다.
이를 이용하면 두 개의 피라미드 타입을 어렵지 않게 구할 수 있다.

다음은 두 개의 피라미드와 입력 피라미드를 비교해서 최소 사용 횟수를 출력해야 한다.

입력 피라미드와 올바른 피라미드를 비교하면서 스왑을 해줘야 하는데 어떻게 하면 최소로 스왑할 수 있을까?

스왑 했을 때 각 자리가 원하는 숫자로 배치 되는 경우가 최선이 된다.
예를 들어 어떤 자리에 0이 1를 원하고 어떤 자리에 1이 0을 원한다면 이 두 자리를 스왑하는 것은 최선이 선택이 된다.

구현 방법은 다음과 같다.

먼저, 우선 순위가 높은 자리 간 스왑해 주고, 아직 스왑되지 못한 나머지 수를 이용해서 가능한 조건인지 체크하고, 가능하다면 나머지 스왑을 해준다.

가능하지 않은 조건은 다음과 같다.

• 하나의 색상만 남는 경우
• 두개의 색상만 남는 경우 (이 경우는 서로를 원하지 않기 때문에 불가능함)
• 세개의 색상이 남았음에도 각자 원하는 수가 다른 경우

그 외에는 세개의 색상이 같은 개수를 원하고 있으며 서로를 원하지 않고 있다.
예를 들어 다음과 같은 경우다.

0: 0 -> 1 3개 (0은 1를 원하고 있음)
1: 1 -> 2 3개 (1은 2를 원하고 있음)
2: 2 -> 0 3개 (2는 0을 원하고 있음)

이 상태에서는 0과 1를 스왑하고, 2를 0으로 스왑하면 올바른 피라미드가 되기 때문에
스왑 횟수는 (같은 개수 * 2)가 된다.

마지막으로 서로 원하는 색상끼리 스왑한 횟수와 더해주면 총 횟수가된다.

이 풀이의 연산은 50만 정도 된다. 피라미드의 각 블록을 한번씩 방문하기 때문이다.

소스 코드

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

class Block {
    int A, cnt;
    Block(int A, int cnt) {
        this.A = A;
        this.cnt = cnt;
    }
}

public class Main {
    static int N;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        if (N == 1) {
            System.out.println(0);
            return;
        }

        int[] rpNum = new int[3]; //반복되는 길이 3 수열
        int[][][] pyramid = new int[3][N][N]; //0은 원본, 1은 type1, 2는 type2
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j <= i; j++) {
                pyramid[0][i][j] = Integer.parseInt(st.nextToken());
            }

            if (i <= 1) {
                if (i == 1) {
                    //1층과 2층이 세 가지 색으로 이루어져 있는지 검사해야 됨
                    rpNum[0] = pyramid[0][1][1];
                    rpNum[1] = pyramid[0][0][0];
                    rpNum[2] = pyramid[0][1][0];

                    if (!check(rpNum)) {
                        System.out.println(-1);
                        return;
                    }

                    setTypesPyramid(pyramid); //type1 type2 피라미드 2층까지 채우기
                }
                continue;
            }

            //type1과 type2 채우기
            for (int j = 0; j <= i; j++) {
                pyramid[1][i][j] = rpNum[j % 3];
            }

            for (int j = 0; j <= i; j++) {
                pyramid[2][i][j] = pyramid[1][i][i - j];
            }

            rpNum = getNextRpNum(rpNum);
        }

        //비교해 준다.
        int answer = Integer.MAX_VALUE;
        for (int k = 1; k <= 2; k++) {
            int cnt = 0;
            for (int i = 0; i < N; i++) {
                //먼저 swapList를 생성해 준다.
                int[][] swapList = new int[3][3]; // [A][B] A를 B로 스왑해야 됨
                for (int j = 0; j <= i; j++) {
                    if (pyramid[0][i][j] != pyramid[k][i][j]) {
                        int A = pyramid[0][i][j];
                        int B = pyramid[k][i][j];
                        swapList[A][B] += 1;
                    }
                }
                //우선적으로 서로 원하는 블록끼리
                for (int j = 0; j < 3; j++) {
                    for (int l = 0; l < 3; l++) {
                        if (swapList[j][l] > 0) {
                            int pair = Math.min(swapList[j][l], swapList[l][j]);
                            swapList[j][l] -= pair;
                            swapList[l][j] -= pair;
                            cnt += pair;
                        }
                    }
                }

                //남아 있는 개수가 전부 같아야됨.
                int left = findLeft(swapList);
                if (left == -1) {
                    System.out.println(-1);
                    return;
                }

                cnt += left * 2; //한 번씩 스왑되기 때문에

            }
            answer = Math.min(answer, cnt);
        }
        System.out.println(answer);

    }

    static int findLeft(int[][] swapList) {
        ArrayList < Block > list = new ArrayList < > ();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (swapList[i][j] > 0) {
                    if (list.size() != 0 && list.get(list.size() - 1).A == i) {
                        return -1;
                    }
                    list.add(new Block(i, swapList[i][j]));
                }
            }
        }
        if (list.size() <= 2) {
            if (list.size() == 0) {
                return 0;
            }
            return -1;
        }

        int left = list.get(0).cnt;
        for (int i = 1; i < list.size(); i++) {
            if (left != list.get(i).cnt) {
                return -1;
            }
        }
        return left;
    }

    static int[] getNextRpNum(int[] rpNum) {
        int[] nextRpNum = new int[3];
        nextRpNum[0] = rpNum[1];
        nextRpNum[1] = rpNum[2];
        nextRpNum[2] = rpNum[0];
        return nextRpNum;
    }


    static boolean check(int[] rpNum) {
        boolean ck[] = new boolean[3];
        for (int i = 0; i < 3; i++) {
            if (ck[rpNum[i]]) {
                return false;
            }
            ck[rpNum[i]] = true;
        }
        return true;
    }

    static void setTypesPyramid(int[][][] pyramid) {
        pyramid[1][0][0] = pyramid[0][0][0];
        pyramid[2][0][0] = pyramid[0][0][0];

        pyramid[1][1][0] = pyramid[0][1][0];
        pyramid[1][1][1] = pyramid[0][1][1];

        pyramid[2][1][0] = pyramid[0][1][1];
        pyramid[2][1][1] = pyramid[0][1][0];
    }
}