[백준/JAVA] 2630번: 색종이 만들기

🔺 문제

2630번: 색종이 만들기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int white = 0, blue = 0;
    static int[][] map;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        map = new int[N + 1][N + 1];
 
        // 입력 받기
        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());
            }
        }
        
        // 🔔 분할 정복 🔔
        partition(0, 0, N);
        
        System.out.println(white);
        System.out.println(blue);
    }
    
    // 🔔 분할 정복  → 재귀
    private static void partition(int row, int col, int size) {
        // 색상이 모두 같은 경우, 실행하고 종료
        if(colorChk(row, col, size)) {
            if(map[row][col] == 0)  white++;
            else                    blue++;
            
            return;
        }
        
        // ⭐ 색상이 모두 같지 않은 경우, 재귀 호출 ⭐
        int newSize = size / 2;    // 사이즈 절반으로 만들기
 
        partition(row,           col,           newSize);   // 좌측상단
        partition(row,           col + newSize, newSize);   // 좌측하단
        partition(row + newSize, col,           newSize);   // 우측상단
        partition(row + newSize, col + newSize, newSize);   // 우측하단
    }
    
    // 색상이 모두 같은지 확인하는 메소드
    private static boolean colorChk(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) { // 색이 다르면 4분할하게 false 반환
                    return false;
                }
            }
        }
        return true;
    }
}
 

✅ 해결 아이디어
✔ 분할 정복 → 재귀 함수 사용
- 각 영역 4개로 나누기
 1. (x,          y,          n/2)
 2. (x + n/2, y,          n/2)
 3. (x,          y + n/2, n/2)
 4, (x + n/2, y + n/2, n/2)

- 해당 영역 안에서 색이 다 같으면, 흰색/파란색 개수에 추가
- 색이 같지 않으면, 또 4가지 경우 수로 분할해 탐색 (재귀)

 

---

🔺 다른 풀이들

- 다들 비슷하심

 

---

💬 느낀 점

재귀.. 분할정복... 넘 약한 부분이다...

또 문제를 열심히 풀어봐야겠다...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

과정까지 그림으로.. 최고....👏👏

[백준] 2630번 색종이 만들기 자바 (분할정복)

[BAEKJOON] 2630 색종이 만들기 - JAVA