색종이 만들기

문제

• 문제 유형 : 분할정복

색종이를 절반씩 나누어서, 같은 영역이 될때까지 나눈다. 같은 영역이 됐다면 count+1을 해준다.

문제 풀이

대표적인 분할정복 문제이다.

로직은 다음과 같다.

 

1. n값과 시작위치를 입력값으로 받는다.

2. 맵이 시작위치부터 n까지 전부 같은 값으로 이루어져있는지 확인한다.

2-1). 만약 전부 같은 값으로 이루어졌다면, 1인지 0인지 확인하고 해당 숫자를 1증가시켜준다.

3. 사방으로 나누어서 함수를 재귀 호출한다. 이 때, 넘기는 n의 값은 n/2이다.

 

→ 맵이 전부 같은 지 확인하는 부분을 두 방법으로 풀었다.

 

1번 방법 )

for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        if(map[x+i][y+j] == 1) b++;
        if(map[x+i][y+j] == 0) w++;
    }
}

if(b == n*n || w ==n*n ){
    if(b>w) blue++;
    else white++;
    return ;
}

 

2번 방법 )

if(n==1 || isSame(n,x,y)){
    if(map[x][y] == 1) blue++;
    if(map[x][y] == 0) white++;
    return ;
}

static boolean isSame(int n,int x,int y){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(map[x][y] != map[x+i][y+j]) return false;
        }
    }
    return true;
}

실수한 부분

1. if(b == n*n || w == n*n )

if(b == n*n || w ==n*n ){
    if(b>w) blue++;
    else white++;
    return ;
}

이 부분을 b == n || w == n 으로 실수해서 생각했다.

 

2. map[x+i][y+i]

static boolean isSame(int n,int x,int y){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(map[x][y] != map[x+i][y+j]) return false;
        }
    }
    return true;
}

이 부분을 map[x+i][x+j] 로 x를 두번 적었다.

코드 1번 풀이

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
    static int N;
    static int[][] map;

    static int blue; // 1
    static int white; // 0

    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        map = new int[N][N];

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                map[i][j] = sc.nextInt();
            }
        }

        half(N,0,0);

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

    private static void half(int n, int x, int y) {
        int b=0;
        int w=0;

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(map[x+i][y+j] == 1) b++;
                if(map[x+i][y+j] == 0) w++;
            }
        }

        if(b == n*n || w ==n*n ){
            if(b>w) blue++;
            else white++;
            return ;
        }

        half(n/2,x,y);
        half(n/2,x+n/2,y+n/2);
        half(n/2,x+n/2,y);
        half(n/2,x,y+n/2);
    }
}

 코드 2번 풀이

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class MainV2 {
    static int N;
    static int[][] map;

    static int blue; // 1
    static int white; // 0

    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        map = new int[N][N];

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                map[i][j] = sc.nextInt();
            }
        }

        half(N,0,0);

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

    private static void half(int n, int x, int y) {
        if(n==1 || isSame(n,x,y)){
            if(map[x][y] == 1) blue++;
            if(map[x][y] == 0) white++;
            return ;
        }

        half(n/2,x,y);
        half(n/2,x+n/2,y+n/2);
        half(n/2,x+n/2,y);
        half(n/2,x,y+n/2);
    }

    static boolean isSame(int n,int x,int y){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(map[x][y] != map[x+i][y+j]) return false;
            }
        }
        return true;
    }
}

코드 3번 풀이

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

public class MainV3 {
    static int N;
    static int[][] map;

    static int blue; // 1
    static int white; // 0

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

        N = Integer.parseInt(br.readLine());

        map = new int[N][N];

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

        half(N,0,0);

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

    private static void half(int n, int x, int y) {
        if(n==1 || isSame(n,x,y)){
            if(map[x][y] == 1) blue++;
            if(map[x][y] == 0) white++;
            return ;
        }

        half(n/2,x,y);
        half(n/2,x+n/2,y+n/2);
        half(n/2,x+n/2,y);
        half(n/2,x,y+n/2);
    }

    static boolean isSame(int n,int x,int y){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(map[x][y] != map[x+i][y+j]) return false;
            }
        }
        return true;
    }
}

N이 최대 2^7 ( 128 ) 이라서, bufferedReader를 사용하면 시간이 크게 준다.