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

 
www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

색종이 만들기 문제와 매우 유사한 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

이 문제는 결코 어렵지 않다.

 

이전에 색종이 만들기 문제를 풀어보았다면 매우 쉽게 풀 수 있었을 것이다. 기본적인 쿼드트리 방식 문제를 변형한 것인지라 혹시 접근 방법을 모르곘다면 아래 두 문제를 먼저 풀이 방법을 보고 오는 것을 추천드린다.

 

st-lab.tistory.com/227

[백준] 2630번 : 색종이 만들기 - JAVA [자바]

 

st-lab.tistory.com/230

[백준] 1992번 : 쿼드트리 - JAVA[자바]

 

 

 

 

이전까지는 공간을 4개로 분할하여 풀어내는 방식인 '쿼드 트리(Quad-Tree)' 을 활용하여 풀었다.

 

 

이 번에는 문제가 하나의 공간을 4개로 분할하는 것이 아닌 9개로 분할하여 풀어내는 문제다.

(이러한 방식을 뭐라하는지는 모르겠다.. Nona-Tree...?)

 

 

일단 문제를 보기 쉽게 이미지로 생각해보자. 위 문제에서의 예제를 토대로 0은 하얀색, 1은 검은색, -1은 회색으로 대체하여 표현해보았다.

 

 

일단 위 공간 전체가 동일안 색상이 아닌 것은 알 수 있다. 그러면 이제 공간을 나누어야 겠지 않겠는가?

 

여기서 이전문제와는 달리 9개의 영역으로 나누어야 한다.

즉, 현재 공간의 크기인 9×9 사이즈에서 가로와 세로를 3으로 나눈 3×3 사이즈 블럭으로 총 9개를 얻을 수 있다.

 

 

쉽게 보자면 다음과 같이 나눠진다는 것이다.

 

 

 

그러면 왼쪽부터 차례대로 한번 보자. 분할 된 1, 2, 3, 4, 5, 6번 공간은 모두 한 개의 색상으로 이루어져 있다.

즉, 해당 색상의 종이 개수를 세자면 흰색 3개(1, 5, 6), 검은색 2개(2, 4), 회색 1개(3)가 되는 것이다.

 

그리고 나머지 7, 8, 9번 공간은 같은색상으로 이루어진 공간이 아니기에 해당 공간을 또다시 9개로 분할해주어야 한다.

각 타일은 3×3 크기였으므로, 해당 크기의 가로 및 세로를 3으로 나누면 1×1 사이즈의 공간을 얻을 수 있다.

 

그러면 다음과 같이 분할되게 된다.

 

 

 

 

이런식으로 각 영역에 따라 색이 같은 색으로 이루어져있는지 검사를 하고, 만약 같지 않다면 9개로 분할, 같다면 해당 색상의 카운트를 증가시키면 된다.

 

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

이전 포스팅과 여타 다를 바 없이 아래와 같이 2가지 입력 방법을 통해 성능을 비교해보려 한다.

 

 

1. Scanner

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;

public class Main {

	public static int[][] board;
	public static int GRAY = 0;		// -1에 해당
	public static int WHITE = 0;	// 0에 해당
	public static int BLACK = 0;	// 1에 해당

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int N = in.nextInt();
		board = new int[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = in.nextInt();
			}
		}

		partition(0, 0, N);

		System.out.println(GRAY);	// -1
		System.out.println(WHITE);	// 0
		System.out.println(BLACK);	// 1

	}

	
	public static void partition(int row, int col, int size) {

		// 만약 같은 색상으로 이루어져있다면 해당 색상 카운트를 증가시킨다.
		if (colorCheck(row, col, size)) {
			if(board[row][col] == -1) { 
				GRAY++;
			}
			else if(board[row][col] == 0) {
				WHITE++;
			}
			else {
				BLACK++;
			}

			return;
		}

		int newSize = size / 3;
		
		partition(row, col, newSize);								// 왼쪽 위
		partition(row, col + newSize, newSize);						// 중앙 위
		partition(row, col + 2 * newSize, newSize);					// 오른쪽 위
		
		partition(row + newSize, col, newSize);						// 왼쪽 중간
		partition(row + newSize, col + newSize, newSize);			// 중앙 중간
		partition(row + newSize, col + 2 * newSize, newSize);		// 오른쪽 중간
		
		partition(row + 2 * newSize, col, newSize);					// 왼쪽 아래
		partition(row + 2 * newSize, col + newSize, newSize);		// 중앙 아래
		partition(row + 2 * newSize, col + 2 * newSize, newSize);	// 오른쪽 아래

	}

	// 해당 영역이 같은 색인지 검사하는 메소드
	public static boolean colorCheck(int row, int col, int size) {
		int color = board[row][col];

		// 각 블럭의 시작점(row, col)부터 블럭의 끝(row + size, col + size)까지 검사
		for (int i = row; i < row + size; i++) {
			for (int j = col; j < col + size; j++) {
				if (color != board[i][j]) {
					return false;
				}
			}
		}
		return true;
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

앞서 말했듯 9개의 영역으로 나누어야 하기 떄문에 각 나눠진 파티션은 원래 크기의 1/3씩 감소한다. 이점 유의하면서 9개의 호출을 빠짐없이 해주도록 해야한다.

 

그리고 필자가 알고리즘 설명에서 이해하기 쉽게 색상으로 표현했기 때문에 각 -1, 0, 1을 카운트하는 변수들을 GRAY, WHITE, BLACK 이름으로 두었다. 이 점 유의하시길 바란다.

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 색상을 입력하는 과정에서 공백을 구분하기 위해 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

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

public class Main {

	public static int[][] board;
	public static int GRAY = 0;		// -1
	public static int WHITE = 0;	// 0
	public static int BLACK = 0;	// 1

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		board = new int[N][N];
		StringTokenizer st;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		partition(0, 0, N);

		System.out.println(GRAY);	// -1
		System.out.println(WHITE);	// 0
		System.out.println(BLACK);	// 1

	}

	
	public static void partition(int row, int col, int size) {

		// 만약 같은 색상으로 이루어져있다면 해당 색상 카운트를 증가시킨다.
		if (colorCheck(row, col, size)) {
			if(board[row][col] == -1) { 
				GRAY++;
			}
			else if(board[row][col] == 0) {
				WHITE++;
			}
			else {
				BLACK++;
			}

			return;
		}

		int newSize = size / 3;
		
		partition(row, col, newSize);								// 왼쪽 위
		partition(row, col + newSize, newSize);						// 중앙 위
		partition(row, col + 2 * newSize, newSize);					// 오른쪽 위
		
		partition(row + newSize, col, newSize);						// 왼쪽 중간
		partition(row + newSize, col + newSize, newSize);			// 중앙 중간
		partition(row + newSize, col + 2 * newSize, newSize);		// 오른쪽 중간
		
		partition(row + 2 * newSize, col, newSize);					// 왼쪽 아래
		partition(row + 2 * newSize, col + newSize, newSize);		// 중앙 아래
		partition(row + 2 * newSize, col + 2 * newSize, newSize);	// 오른쪽 아래

	}

	// 해당 영역이 같은 색인지 검사하는 메소드
	public static boolean colorCheck(int row, int col, int size) {
		int color = board[row][col];

		// 각 블럭의 시작점(row, col)부터 블럭의 끝(row + size, col + size)까지 검사
		for (int i = row; i < row + size; i++) {
			for (int j = col; j < col + size; j++) {
				if (color != board[i][j]) {
					return false;
				}
			}
		}
		return true;
	}

}

 

 

 

색종이나 쿼드트리를 정확하게 이해하고 풀었다면 크게 어려울 것은 없을 것이다. 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 28059037  -  방법 2 : BufferedReader

채점 번호 : 28059033  -  방법 1 : Scanner

 

 

 

 

N 입력으로 들어가는 것이 최대 3⁷, 즉 2187이고 N×N의 블럭을 갖게되면 최대 4782969번을 반복적으로 입력받기 때문에 시간이 많이 소요되는 것을 볼 수 있다.

 

 

 

---

• 정리

 

이 번 문제 또한 어려운 점은 없었을 것이다.

이미지에 대한 기본적인 분할 방식이라 그림으로 보면 직관적으로 이해가 빠르게 될 것이다. 이 후 문제들은 이러한 개념을 이제 어떻게 활용해야하는가의 문제라 개념을 정확하게 알고가시길 바란다.

 

혹여 어렵거나 이해가 가지 않는 부분이 있다면 댓글로 남겨주시길 바란다.