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

▶ 문제

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

1780번: 종이의 개수

 

▶ 설명

색종이 만들기 문제의 변형된 문제이다.
색종이 만들기에서는 만족하는 결과가 아니면 4등분으로 분할하는 반면, 이 문제는 9등분으로 분할하여 재귀함수를 통해 다시 탐색하여야 한다.

 

그림으로 살펴보자면 아래와 같다.

1) 모두 같은 값일 때 탐색 종료

2) 같은 값이 아닐 때 분할하여 다시 탐색

 

 

 

같은 값으로 되어 있지 않아 9등분으로 분할하면 원래 row와 column의 길이에서 3으로 나누어 주어야 한다.

원래 길이가 9라고 한다면  3씩 row와 column을 나누어 주고 9개의 조각을 차례로 탐색하게 된다.

탐색할 때마다 시작하는 인덱스는 각각 아래와 같다.

그리고 위의 인덱스를 x와 y로 치환하여 다시 정리해 보면 아래와 같다.

위의 시작 인덱스들을 재귀 함수의 인수로 넣어주면 새롭게 같은 값인지 탐색을 할 수 있는 세팅이 마련된다.

나는 마치 BFS에서 dx,dy 처럼 x,y로 각각 나누어 9개로 이루어진 배열을 만들어 반복문을 통해 쌍으로 재귀함수에 호출할 수 있게 코드로 구현하였다.

배열로 만들지 않더라도 9번의 재귀 함수를 호출하기만 하면 된다.

 

이 설명을 바탕으로 코드를 구성하면 아래와 같다.

 

 

▶ 문제 풀이

🌱 풀이

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

public class Main {
	static int nOne = 0;
	static int zero = 0;
	static int pOne = 0;
	static int[][] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		arr = new int[n][n];
		StringTokenizer st;
        //2차 배열로 입력 값 저장하기.
		for (int i = 0; i < arr.length; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < arr[i].length; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		figureCnt(0, 0, n); //첫 인덱스 0,0과 row/column의 길이인 n 을 인수로 넣기.

		System.out.println(nOne + "\n" + zero + "\n" + pOne);
	}

	private static void figureCnt(int x, int y, int size) {
		if (sameNum(x, y, size)) {
			if (arr[x][y] == -1) {
				nOne++; //negative 1 (-1)
			} else if (arr[x][y] == 0) {
				zero++; // 0
			} else if (arr[x][y] == 1) {
				pOne++; // positive 1 (+1)
			}

		} else {
			int resize = size / 3;

			int[] xIdx = { x, x, x, x + resize, x + resize, x + resize, 
					x + (resize * 2), x + (resize * 2), x + (resize * 2) };
			int[] yIdx = { y, y + resize, y + (resize * 2), y, y + resize, 
					y + (resize * 2), y, y + resize, y + (resize * 2) };

			for (int i = 0; i < 9; i++) {
				figureCnt(xIdx[i], yIdx[i], resize);
			}
		}
	}

	private static boolean sameNum(int x, int y, int size) {
		if (size == 1) {
			return true;
		} else {
        //row나 column의 길이가 2 이상일 경우.
        //첫 인덱스의 값을 기준으로 다른 값과 같은지 비교하기.
			int firstIdx = arr[x][y];

			for (int i = x; i < x + size; i++) {
				for (int j = y; j < y + size; j++) {
                //다른 값이 검색되면 false를 반환하여 다시 9등분 하도록 보내기.
					if (arr[i][j] != firstIdx) {
						return false;
					}
				}
			}
            //다른 값이 검색되지 않았다면 true를 반환하기.
			return true;
		}

	}

}