[백준] no2630: 색종이 만들기

문제

0과 1로만 이루어진 정사각 배열이 주어진다.( 길이는 무조건 짝수로 주어진다. )

배열을 순회하며 만약 다른 숫자가 포함되어 있으면, 사등분 해서 다시 순회한다.

만약 순회한 부분 배열이 모두 같은 숫자일 경우, 더이상 자르지 않는다.

모두 0으로 같으면 흰종이로, 1이면 파란종이로 친다.

최소한으로 잘라서 흰종이와 파란종이의 개수를 차례대로 출력한다.

 

문제 링크 : https://www.acmicpc.net/problem/2630

---

원리

필자는 BFS로 해결했다.

---

풀이방법

1. 입력된 배열을 map[][]으로 받는다.

2. 각 시작 노드와 검사할 길이를 받을 int[] 혹은 클래스를 만든다. (필자는 Node라는 class 사용함)

3. 검사해야할 부분 배열의 Node를 넣을 대기열을 만든다. 필자는 ArrayDeque를 사용했다.

4. 검사 시작을 위해 대기열에 첫 번째 Node를 넣어준다.

5. 이제 대기열이 쫑날까지 신나게 돌려주면 된다.

6. 이중반복으로 각 시작점에서부터 주어진 길이만큼 부분 이중 배열을 순회한다.

7. 중간에 다르면 4등분해서 각 시작점과 반토막난 검사 길이를 Node로 만들어 대기열에 담아준다.

8. 만약 다를 경우엔 반복을 멈춰줘야 한다. 안그럼 대기열 폭발한다.

9. 만약 다 통과하면(통과 했는지, 그냥 반복이 끝난건지 표시 필요) 첫 번째 인자를 기준으로 0인지 1인지 맞춰서 카운트

0. BFS 끝났으면 0(white)과 1(blue)의 개수를 출력

 

---

나의 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class no2630 {

    private static int[][] map;
    private static int T;
    private static int white;
    private static int blue;

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

        T = Integer.parseInt(br.readLine());
        map = new int[T][T];
        for(int i=0; i<T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<T;j++) {
                map[i][j]= Integer.parseInt(st.nextToken());
            }
        }
        BFS();

        System.out.println(white);
        System.out.println(blue);
    }

    private static void BFS() {
        Deque<Node> dq = new ArrayDeque<>();
        Node first = new Node(0,0, T);
        dq.add(first);

        while(!dq.isEmpty()) {
            Node now = dq.poll();
            int nowX = now.X;
            int nowY = now.Y;
            int start = map[nowX][nowY];
            int howMany = now.Length;
            boolean stop = false;
            for(int i = 0; i < howMany; i++) {
                for(int j = 0; j < howMany; j++) {
                    if(map[nowX+i][nowY+j]!=start) {
                        dq.add(new Node(nowX, nowY, howMany / 2));
                        dq.add(new Node(nowX + howMany / 2, nowY, howMany / 2));
                        dq.add(new Node(nowX, nowY + howMany / 2, howMany / 2));
                        dq.add(new Node(nowX + howMany / 2, nowY + howMany / 2, howMany / 2));
                        stop = true;
                        break;
                    }
                }
                if(stop) break;
            }
            if(!stop) {
                if (start == 0) white++;
                else blue++;
            }
        }
    }

    private static class Node {
        private int X;
        private int Y;
        private int Length;
        public Node(int x, int y, int length) {
            this.X = x;
            this.Y = y;
            this.Length = length;
        }
    }
}