백준 문제풀이

[Baekjoon 2630] 색종이 만들기 - JAVA

planting grass 2023. 5. 27. 15:32
728x90

[Silver II] 색종이 만들기 - 2630

문제 링크

성능 요약

메모리: 17188 KB, 시간: 196 ms

분류

분할 정복, 재귀

문제 설명

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

문제 풀이

분할 정복 알고리즘을 사용하여 재귀적으로 색종이를 분할하고, 각 영역의 개수를 세는 문제입니다.

알고리즘은 아래와 같다.

주어진 종이를 자르는 규칙에 따라 재귀적으로 분할하면서 각 영역의 색상을 확인한다. 만약 영역이 모두 같은 색으로 칠해져 있다면 해당 색상의 개수를 증가시킨다. 그렇지 않다면 영역을 4개의 작은 정사각형으로 나누어 각각에 대해 재귀적으로 동일한 과정을 수행한다.

분할 과정에서는 현재 영역의 크기를 계산하고, 4개의 작은 정사각형의 시작 좌표를 정하고 재귀적으로 호출한다. 이러한 분할 작업은 영역의 크기가 1이 될 때까지 반복된다.

마지막으로 재귀 호출이 종료된 후, 흰색과 파란색 영역의 개수를 출력한다.

이를 위한 countColors 메소드와 isSameColor 메소드를 구현했다.

public class Main {

    static int[][] paperColors;
    static int whiteCount = 0;
    static int blueCount = 0;

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

        int n = Integer.parseInt(br.readLine());
        paperColors = new int[n][n];

        // 색종이 색상 정보 입력 받기
        for (int i = 0; i < paperColors.length; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < paperColors[i].length; j++) {
                paperColors[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        countColors(0, 0, n); // 색상 개수 세기
        System.out.println(whiteCount + "\n" + blueCount); // 결과 출력
    }

    // 색종이의 색상 개수 세는 메소드
    private static void countColors(int x, int y, int size) {
        if (isSameColor(x, y, size)) {
            if (paperColors[x][y] == 1) {
                blueCount++; // 파란색일 경우 파란색 개수 증가
            } else {
                whiteCount++; // 흰색일 경우 흰색 개수 증가
            }
        } else {
            int halfSize = size / 2;
            int[] startX = { x, x, x + halfSize, x + halfSize };
            int[] startY = { y, y + halfSize, y, y + halfSize };

            // 4개의 작은 정사각형으로 분할하여 재귀적으로 색상 개수 세기
            for (int i = 0; i < 4; i++) {
                countColors(startX[i], startY[i], halfSize);
            }
        }
    }

    // 주어진 영역이 같은 색상인지 확인하는 메소드
    private static boolean isSameColor(int x, int y, int size) {
        if (size == 1) {
            return true; // 영역이 크기 1이면 같은 색상이므로 true 반환
        } else {
            int color = paperColors[x][y]; // 현재 영역의 색상 저장
            for (int i = x; i < x + size; i++) {
                for (int j = y; j < y + size; j++) {
                    if (paperColors[i][j] != color) {
                        return false; // 영역 내의 색상이 다르면 false 반환
                    }
                }
            }
            return true; // 영역 내의 색상이 모두 같으면 true 반환
        }
    }
}

코드 풀이

static int[][] paperColors;
    static int whiteCount = 0;
    static int blueCount = 0;

paperColors는 색종이의 색상 정보를 저장하는 용도로, whiteCount는 흰색 영역의 개수를 저장하는 용도로, blueCount는 파란색 영역의 개수를 저장하는 용도로 2차원 배열을 선언한다.

        int n = Integer.parseInt(br.readLine());
        paperColors = new int[n][n];

사용자로부터 색종이의 크기 n을 입력받고, paperColors 배열을 크기 n으로 초기화한다.

        for (int i = 0; i < paperColors.length; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < paperColors[i].length; j++) {
                paperColors[i][j] = Integer.parseInt(st.nextToken());
            }
        }

이 부분은 사용자로부터 색종이의 색상 정보를 입력받는 부분이다.

각 줄마다 공백을 기준으로 숫자를 입력받아 paperColors 배열에 저장한다.

        countColors(0, 0, n); // 색상 개수 세기
        System.out.println(whiteCount + "\n" + blueCount); // 결과 출력
    }

countColors 메소드를 호출하여 색종이의 색상 개수를 세고, 그 결과를 출력한다.

    private static void countColors(int x, int y, int size) {
        if (isSameColor(x, y, size)) {
            if (paperColors[x][y] == 1) {
                blueCount++; // 파란색일 경우 파란색 개수 증가
            } else {
                whiteCount++; // 흰색일 경우 흰색 개수 증가
            }
        } else {
            int halfSize = size / 2;
            int[] startX = { x, x, x + halfSize, x + halfSize };
            int[] startY = { y, y + halfSize, y, y + halfSize };

            // 4개의 작은 정사각형으로 분할하여 재귀적으로 색상 개수 세기
            for (int i = 0; i < 4; i++) {
                countColors(startX[i], startY[i], halfSize);
            }
        }
    }

countColors 메소드는 재귀적으로 색상 개수를 세는 메소드다.

주어진 영역 (x, y)에서 크기 size의 색종이를 검사한다.

영역이 같은 색상인 경우 해당 색상의 개수를 증가시키고, 그렇지 않은 경우 영역을 4개의 작은 정사각형으로 분할하여 재귀적으로 countColors 메소드를 호출한다.

    private static boolean isSameColor(int x, int y, int size) {
        if (size == 1) {
            return true; // 영역이 크기 1이면 같은 색상이므로 true 반환
        } else {
            int color = paperColors[x][y]; // 현재 영역의 색상 저장
            for (int i = x; i < x + size; i++) {
                for (int j = y; j < y + size; j++) {
                    if (paperColors[i][j] != color) {
                        return false; // 영역 내의 색상이 다르면 false 반환
                    }
                }
            }
            return true; // 영역 내의 색상이 모두 같으면 true 반환
        }
    }

isSameColor 메소드는 주어진 영역의 색상이 모두 같은지를 확인하는 메소드다.

만약 영역의 크기가 1이면 해당 영역은 같은 색상이므로 true를 반환한다.

아닌 경우 영역 내의 모든 색상을 비교하여 다른 색상이 있으면 false를 반환하고, 모든 색상이 같으면 true를 반환한다.

728x90
저작자표시