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

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

1780번: 종이의 개수

 

 

 

 

---

 

 

 

 

 

 

---

 

문제

3ⁿ 꼴인 N을 입력받은 N * N 크기의 종이에 -1, 0, 1 중 하나가 저장되어 있고 다음 2가지의 규칙을 따라 종이를 자른다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

 

N x N 크기의 종이

1. 종이가 모두 같은 수로 되어있다면 이 종이를 그대로 사용

 

N x N 크기의 종이 9등분

2. (1)이 아닌 경우에는 9등분하여 1의 과정을 반복

 

 

 

 

 

---

 

 

 

 

 

문제풀이

보자마자 분할정복, 재귀 알고리즘으로 해결하면 금방 풀겠다고 생각했다.

 

2차원배열 paper를 매개변수로 받아 모두 같은지 확인하는 메소드 isAllSamePaperNum

2차원배열 paper를 매개변수로 받아  isAllSamePaperNum로 확인 후 모두 같지 않으면 규칙 (2)처럼 9등분하는 메소드 cutPaper

이렇게 2개의 메소드를 선언하였다.

 

문제점

isAllSamePaperNum 메소드에서 종이가 모두 같은 수로 되어있는지 확인하는 로직을 구현할 때 set을 이용해서 구현하였는데, 조건에 심각한 오류가 있어서 쉬운 문제임에도 불구하고 많은 시간이 걸렸다...

 

해결방안

set을 이용해서 모두 같은 숫자인지 확인하는 로직 조건에서 같은 숫자면 set의 사이즈가 1일 것이라고만 생각해서 모두 같은 숫자인지 판별하는 조건을 추가해주었다.

 

보자마자 구현방법이 생각날만큼 쉬운 문제 였지만, 꼼꼼히 확인하는 습관을 더 들여야겠다.

 

 

 

 

 

---

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;

public class bj_1780 {
	private static int countN = 0, countZ = 0, countP = 0; // -1 , 0 , 1
	
	private static final int cutCount = 9;

	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			int n = Integer.parseInt(br.readLine());
			Integer[][] paper = new Integer[n][n];
			
			
			for(int i=0; i<n; i++) {
				String[] paperStr = br.readLine().split(" ");
				
				for(int j=0; j<paperStr.length; j++) {
					paper[i][j] = Integer.parseInt(paperStr[j]);
				}
			}
			
			cutPaper(paper);
			
			System.out.println(countN);
			System.out.println(countZ);
			System.out.println(countP);
			
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	
	public static void cutPaper(Integer[][] paper) {
		if(paper == null || paper.length < 1)
			return;
		
		if(isAllSamePaperNum(paper)) {
			if(paper[0][0] < 0)
				countN++;
			else if(paper[0][0] == 0)
				countZ++;
			else
				countP++;
		} else {
			int newSize = paper.length / 3;
			
			for(int i=0; i<cutCount; i++) {
				int xStartPoint = newSize * (i / 3); // 0 0 0 9 9 9 18 18 18
				int yStartPoint = newSize * (i % 3); // 0 3 6 0 3 6 0 3 6
				Integer[][] newPaper = new Integer[newSize][newSize];
				int xIndex = 0;
				int yIndex = 0;
				
				for(int j=xStartPoint; j<xStartPoint + newSize; j++) {
					for(int k=yStartPoint; k<yStartPoint + newSize; k++) {
						newPaper[xIndex][yIndex++] = paper[j][k];
					}
					xIndex++;
					yIndex = 0;
				}
				
				cutPaper(newPaper);
			}
		}
	}
	
	public static boolean isAllSamePaperNum(Integer[][] paper) {
		int num = paper[0][0];
		
		for(int i=0; i<paper.length; i++) {
			for(int j=0; j<paper[i].length; j++) {
				if(num != paper[i][j]) {
					return false;
				}
			}
		}
		
		return true;
	}
}