색종이 만들기(2630)

색종이 만들기(2630)

import java.io.*;
import java.util.*;

public class Main {
  
  static int[][] nemo;
  static int wCnt = 0;
  static int bCnt = 0;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int n =  Integer.parseInt(br.readLine());
    
    nemo = new int[n+1][n+1];
    
    for(int i = 1; i <= n; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());

      for(int j = 1; j <= n; j++) {
        nemo[i][j] = Integer.parseInt(st.nextToken());
      }
    }
    
    check(1, 1, n);
    
    sb.append(wCnt).append("\n").append(bCnt);
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static void check(int rs, int cs, int len) {

    boolean flag = true;
    int val = nemo[rs][cs];
    
    // 네모가 같은 값인지 체크
    for(int r = rs; r <= rs+len-1; r++) {
      for(int c = cs; c <= cs+len-1; c++) {
        if(nemo[r][c] == val) continue;
        else {
          flag = false;
          break;
        }
      }
    }
    
    //네모값이 다 같다면
    if(flag) {
      if(val == 0) wCnt++;
      else bCnt++;
    } else {
      check(rs, cs, len/2); //좌상
      check(rs+len/2, cs, len/2); //우상
      check(rs, cs+len/2, len/2); //좌하
      check(rs+len/2, cs+len/2, len/2); //우하
    }
  }
}

풀이과정

1. 면의 값이 같지 않을 때 4등분으로 분리하는 것을 반복한다는 조건 때문에 재귀함수로 풀기로 생각했다.
2. 네모라는 객체를 생각했을 때, 가로, 세로, 값이라는 속성을 가지고 있을 것으로 생각되었다.
3. 그러면 가로와 세로의 길이를 어떻게 기준점을 세울 것이냐를 생각해서, 일정한 규칙으로 길이가 줄어들고, 시작점과 길이를 알면 끝점을 알 수 있을것으로 생각했다.

- 성공
- 메모리 : 15644 KB
- 시간 : 164 ms

보안점

1. 이번 문제를 풀면서 객체의 속성을 파악하고 그 속성을 활용하여 문제 풀이에 접근하는 방식을 생각해보았다.
2. 하지만 속성 파악 후 어떻게 풀이에 활용할지 계획이 바로 떠오르지 않았다.
3. 속성을 활용하여 이끌어낼 수 있는 전략들을 생각하는 힘을 길러야겠다.