백준 1780. 종이의 개수

🅰 백준 1780. 종이의 개수

1780번: 종이의 개수

✏️ 문제 풀이

• 재귀를 이용하여 문제를 풀어주었다.
• 쿼드트리, 종이자르기 등과 같이 비슷한 문제로 접근하였다.
• 종이를 9개로 나누기 때문에 9개의 시작점을 찾아서 재귀를 돌려주었고, 첫 시작 값을 비교하여 전부 다 같은 숫자이면 각 숫자에 맞는 변수를 ++해줘서 종이의 개수를 count 해주었다.

✏️ 소스코드

package divideandconquer;

import java.util.*;
import java.io.*;
public class Main_실버2_1780_종이의개수 {
	private static int minus,zero,plus;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int 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());
			}
		}
		
		search(map,N,0,0);
		System.out.println(minus);
		System.out.println(zero);		
		System.out.println(plus);
		
	}

	private static void search(int[][] map, int N, int start, int end) {
		boolean check = false;
		int first = map[start][end];
		Loop1 : for (int i = start; i < start+N; i++) {
			for (int j = end; j < end+N; j++) {
				if(map[i][j]!=first) {
					check = true;
					break Loop1;
				}
			}
		}
		
		if(check) {
			N = N/3;
			search(map,N,start,end);
			search(map,N,start,end+N);
			search(map,N,start,end+(2*N));
			search(map,N,start+N,end);
			search(map,N,start+N,end+N);
			search(map,N,start+N,end+(2*N));
			search(map,N,start+(2*N),end);
			search(map,N,start+(2*N),end+N);
			search(map,N,start+(2*N),end+(2*N));
		}
		else if(first == -1) {
			minus++;
		}
		else if(first == 0) {
			zero++;
		}
		else if(first == 1) {
			plus++;
		}
	}
}

 

✅ 후기

•