[백준, JAVA] 1780번 : 종이의 개수

1. 문제

2. 아이디어

색종이 만들기 문제와 상당히 유사하다. (대부분의 코드를 재사용할 수 있었다.)

• 차이점으로는 체크해야 할 변수가 blue white 2개에서, -1, 0 , 1로 3개가 되었다.

• 쪼개는 단위가 절반이 아니라 3분의 1씩 쪼갠다. (newSize = size/3)

  따라서 색종이 만들기 문제에서는 1, 2, 3, 4분면 개념으로 나누어 Divide 함수를 호출 했다면,

  이 문제에서는 키패드와 같이 9분할 개념으로 접근해서 함수를 호출해주기만 하면 된다.

3. 코드

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

public class Main {
	public static int[][] map;
	public static int one;
	public static int zero;
	public static int minus;
	
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        map = new int[N][N];
        StringTokenizer st;
        
        for (int i = 0; i < N; i++) {
        	st = new StringTokenizer(bf.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        divide(0, 0, N);
        System.out.println(minus);
        System.out.println(zero);
        System.out.println(one);
    }
    
    public static void divide(int row, int col, int size) {
    	if(colorCheck(row, col, size)) {
    		if(map[row][col]==0) zero++;
    		
    		else if(map[row][col]==1) one++;
    		
    		else minus++;
    		
    		return;
    	}
    	
    	int newSize = size/3;
    	
    	divide(row, col, newSize); // 키패드 1 위치
    	divide(row, col+newSize, newSize); // 키패드 2 위치
    	divide(row, col+2*newSize, newSize); // 키패드 3 위치
    	
    	divide(row+newSize, col, newSize); // 키패드 4 위치
    	divide(row+newSize, col+newSize, newSize); // 키패드 5 위치
    	divide(row+newSize, col+2*newSize, newSize); // 키패드 6 위치
    	
    	divide(row+2*newSize, col, newSize); // 키패드 7 위치
    	divide(row+2*newSize, col+newSize, newSize); // 키패드 8 위치
    	divide(row+2*newSize, col+2*newSize, newSize); // 키패드 9 위치
    	
    }
    
    public static boolean colorCheck(int row, int col, int size) {
    	int color = map[row][col]; // 시작점(원점)의 색
    	
    	for(int i=row; i<row+size; i++) {
    		for (int j = col; j < col+size; j++) {
    			if(map[i][j]!=color) return false; // 시작점의 색이 무엇이든, 같지 않다면 false
			}
    	}
    	
    	return true;
    }
    
}

4. 느낀점

• 하나의 알고리즘 문제를 풀 때, 비슷한 유형의 문제들을 풀어보는 것이 확실히 좋은 것 같다.

• 분할 정복과 재귀함수 활용에 대해 익숙해져 간다!