BOJ) 종이의 개수 (1780 번)

종이의 개수

1780번: 종이의 개수

N by N 크기의 종이가 있고, 각 칸에는 -1, 0, 1 세 숫자 중 하나가 저장되어있다.

이 종이는 아래의 규칙에 따라 사용한다.

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

2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

위의 규칙에 따라 종이를 잘랐을 때, 각각 -1, 0, 1로만 채워진 종이의 개수를 구하는 문제다.

일단 규칙에 따라서 1번 규칙을 만족하는 메소드를 만들었다.

모든 종이가 가장 첫번째 위치에 있는 칸과 모두 같은지 아닌지 true / false를 리턴해주었다.

 

다음으로는 2번 메소드를 만들어 주었다.

처음으로 주어진 전체 종이, 규칙에 따라 잘려진 종이 모두 1번과 2번에서 다시 사용하기 위해, 종이의 좌측 상단과 우측 하단 지점을 파라메터로 받았다. 어차피 정사각형으로 잘려지기 때문에, 이 두 점으로 종이의 모든 칸을 순회할 수 있다.

종이를 자를 때는, y축의 길이를 3으로 등분해서 잘리게 될 정사각형의 길이를 구해주었다.

이후, 현재 입력받은 종이를 순회하면서, 위에서 구한 길이만큼 증가하면서 잘라낸 종이들의 시작점과 끝점으로 다시 1번 규칙을 검사했다.

 

이를 queue를 통해서 좌표 값을 저장하고, queue에서 빼내서 값을 검사하려고 했는데, 재귀 함수로 짜는 것도, 해석하는 것도 어렵지 않아서 재귀 함수로 만들었다. (정확하게는 재귀함수가 더 적합하다고 느꼈다.)

그리고 -1, 0, 1의 종이 갯수를 리턴해주어야 하기 때문에, 애초에 값을 저장할 때, 0, 1, 2로 1씩 증가해서 저장해줬다. 종이의 갯수를 저장할 int 배열을 선언해서 각각 -1은 0으로, 0은 1로,  1은 2의 인덱스로 저장하며, 저장하고 출력하는 과정을 간편하게 했다.

 

 

 

코드

 

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

public class CountOfPapers_1780 {
  static final int PAPER_LENGTH =3;
  static final String NEW_LINE = "\n";

  static int n;
  static int[] papers;
  static int [][] map;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    map = new int[n+1][n+1]; // 1,1 에서 시작

    for(int y=1; y<=n; y++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int x=1; x<=n; x++) {
        map[y][x] = Integer.parseInt(st.nextToken()) +1;
      }
    }

    br.close();
    solution();
  }

  private static void solution() {
    papers = new int[PAPER_LENGTH];
    find(new Pos(1,1), new Pos(n,n));

    StringBuilder sb = new StringBuilder();
    for(int i=0; i<PAPER_LENGTH; i++) {
      sb.append(papers[i]).append(NEW_LINE);
    }
    System.out.println(sb.toString());
  }

  private static void find(Pos start, Pos end) {
    if(isAllSame(start, end)) {
      int paper = map[start.y][start.x];
      papers[paper]++;
    } else {
      int div = (end.y - start.y +1) /PAPER_LENGTH;
      for(int y = start.y; y <= end.y; y+= div) {
        for(int x = start.x; x<= end.x; x+= div) {
          find(new Pos(x,y), new Pos(x+div-1, y+div-1));
        }
      }
    }
  }

  private static boolean isAllSame(Pos start, Pos end) {
    int paper = map[start.y][start.x];
    for(int y = start.y; y <= end.y; y++) {
      for(int x = start.x; x <= end.x; x++) {
        if(paper != map[y][x]) {
          return false;
        }
      }
    }
    return true;
  }

  private static class Pos {
    int x,y;
    public Pos(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
}