Jungol[1335] - 색종이 만들기

링크

JUNGOL | 색종이 만들기(영역구분) > 문제은행

문제설명

• 분할정복

문제풀이

• 완전하지않으면 4조각내서 각각 완전한지 체크

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;


public class Main1335 {
    public static int[][] map;
    public static int white=0;
    public static int blue=0;
    public static boolean is_clear(int r, int c, int len) {
        int first=map[r][c];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if(first!=map[r+i][c+j]) {
                    return false; 
                }
            }
        }
        if(first==0) {
            white++;
        }
        else if(first==1) {
            blue++;
        }
        return true;
    }

    public static void Search(int r, int c, int len) {
        if(is_clear(r,c,len)) {
            return;
        }
        else {
            Search(r,c,len/2);
            Search(r+len/2,c,len/2);
            Search(r,c+len/2,len/2);
            Search(r+len/2,c+len/2,len/2);
        }
    }
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/jungol/1335.txt"));
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        Search(0,0,N);
        System.out.println(white);
        System.out.print(blue);
    }
}

아쉬운점

• Search안에서 Search를 타고들어가야하는데 is_clear로 타고들어가서 한번만 타고 멈춤

잘한점

• 재귀로 분할정복함
• index실수 없었음