https://www.acmicpc.net/problem/2630
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
www.acmicpc.net
코드설명
분할 정복 문제입니다.
N문제로직입니다.
1. 분할정복을 위한 재귀를 사용합니다.
2. 처음에 각 Size N 만큼 해당 정사각형이 하나의 색종이로 이루어져있는지 확인합니다.
만약 해당 정사각형이 하나의 색종이로 이루어졌다면 1개만 세고 종료시킵니다.
아니라면, 해당 정사각형을 아래와 같이 4사분면을 나누어서 모두 호출합니다.
int nSize = size / 2; //절반씩 줄여나갑니다. //각 4분면 나누어서 처리 divideConquer(r, c, nSize); divideConquer(r, c + nSize , nSize); divideConquer(r + nSize, c, nSize); divideConquer(r + nSize, c + nSize, nSize);
위의 2번 로직을 계속해서 반복하면됩니다.
설명은 코드에 주석으로 담아두었습니다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int N, M; public static int[][] map; public static int answer = 0, answerWhite = 0, answerBlue = 0; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); 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()); } } divideConquer(0, 0, N); System.out.println(answerWhite); System.out.println(answerBlue); } public static void divideConquer(int r, int c, int size) { boolean flag = true; //처음에는 true로 초기화. 이후에 false로 바뀌어있다면, 해당 사각형은 분할정복의 필요성이 존재. int standardColor = map[r][c]; for(int i=r; i<r + size;i++) { for(int j=c; j<c + size;j++) { //색상이 같지 않다면 false if(map[i][j] != standardColor) { flag = false; break; } } } if(flag == true) { if(map[r][c] == 0) { answerWhite += 1; }else if(map[r][c] == 1){ answerBlue += 1; } return ; } int nSize = size / 2; //절반씩 줄여나갑니다. //각 4분면 나누어서 처리 divideConquer(r, c, nSize); divideConquer(r, c + nSize , nSize); divideConquer(r + nSize, c, nSize); divideConquer(r + nSize, c + nSize, nSize); } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 쿼드트리 1992 - 분할정복(DivideAndConquer) JAVA (0) | 2023.10.02 |
---|---|
[백준] 222-풀링 17829 - 분할정복 JAVA (0) | 2023.10.01 |
[백준] 9996 한국이 그리울 땐 서버에 접속하지 - 문자열(String) + 정규표현식(Regular Expression) + 동적계획법(DP, Dynamic Programming) JAVA (0) | 2023.09.28 |
[백준] 6987 월드컵 - 브루트포스(BruteForce) + 조합(Combination) JAVA (0) | 2023.09.27 |
[백준] 1194 달이 차오른다, 가자. - BFS + 비트마스크 JAVA (0) | 2023.09.26 |