[백준] 2630 색종이 만들기(JAVA)

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

2630번: 색종이 만들기

풀이

 필자는 문제를 처음보고 분할 정복과 재귀를 이용하면 쉽게 풀릴것 같다는 생각을 하였다. 이번에는 두개의 코드를 포스팅 할것이다. 우선 첫번째 코드는 내가 짠 코드이고 두번째는 다른 사람들이 짠 코드이다.

 

 첫번째 코드는 우선 처음 메소드에 들어가면 해당사이즈 만큼의 색종이가 하나의 색으로 되어있는지 확인하고 만약 여기서 하나의 색으로만 되어있으면 그자리에서 바로 함수를 종료한다. 만약 그렇지 않다면 이중for문을 통해 2번씩 하여 총 4번을 반복한다. 코드를 보면 조금 난해 할수있다.

 

 두번째 코드는 전체적인 개요는 같으나 이중 for문으로 돌아가는 것이 아닌 하나의 함수에서 제 1234분면을 직접적으로 호출한다. 그 이외의 전체적인 매커니즘은 동일하다

 

코드1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

    public static int[][] map;
    public static int N, B_count = 0, W_count = 0;

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

        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());
            }
        }

        Divide(N, 0, 0);
        System.out.print(W_count + "\n" +B_count);
    }

    public static void Divide(int size, int col, int row) {

        if (check(size , col, row)){
            if(map[(size / 2)][(size / 2)] == 1)
                B_count++;
            else
                W_count++;
            return;
        }

        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                if (check(size / 2, col + (size / 2) * i, row + (size / 2) * j)){
                    if(map[col + (size / 2) * i][row + (size / 2) * j] == 1)
                        B_count++; //1
                    else
                        W_count++;
                }
                else
                    Divide(size / 2, col + (size / 2) * i, row + (size / 2) * j);
            }
        }
    }

    public static boolean check(int size, int col, int row) {
        for (int i = col; i < col + size; i++) {
            for (int j = row; j < row + size; j++) {
                if (map[i][j] != map[col][row]) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

코드2

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
 
public class Main {
	
	// 색상 카운트 할 변수 및 색종이(board)
	public static int white = 0;
	public static int blue = 0;
	public static int[][] board;
 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		board = new int[N][N];
		
		StringTokenizer st;
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			for(int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		partition(0, 0, N);
		
		System.out.println(white);
		System.out.println(blue);
		
	}
	
	public static void partition(int row, int col, int size) {
		
		//
		if(colorCheck(row, col, size)) {
			if(board[row][col] == 0) {
				white++;
			}
			else {
				blue++;
			}
			return;
		}
		
		int newSize = size / 2;	// 절반 사이즈
		// 재귀 호출
		partition(row, col, newSize);						// 2사분면
		partition(row, col + newSize, newSize);				// 1사분면
		partition(row + newSize, col, newSize);				// 3사분면
		partition(row + newSize, col + newSize, newSize);	// 4사분면
	}
	
	
	// 현재 파티션의 컬러가 같은지 체크한다.
	public static boolean colorCheck(int row, int col, int size) {
	
		int color = board[row][col];	// 첫 번째 원소를 기준으로 검사
		
		for(int i = row; i < row + size; i++) {
			for(int j = col; j < col + size; j++) {
				// 색상이 같이 않다면 false를 리턴 
				if(board[i][j] != color) {
					return false;
				}
			}
		}
		// 검사가 모두 통과했다는 의미이므로 true 리턴
		return true;
	}
}