단지번호붙이기(2667)

단지번호붙이기(2667)

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
  
  static int n;
  static int key = 0;
  static boolean[][] map;
  static boolean[][] visited;
  static List<Integer> danji = new ArrayList<>();

  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();
    
    n =  Integer.parseInt(br.readLine());
    
    map = new boolean[n+1][n+1];
    visited = new boolean[n+1][n+1];
    
    for(int i = 0; i < n; i++) {
      char[] ch = br.readLine().toCharArray();
      for (int j = 0; j < n; j++) {
        if (ch[j] == '1') map[i+1][j+1] = true;
      }
    }
    
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= n; j++) {
        if(map[i][j] && !visited[i][j]) {
          danji.add(0);
          check(i, j);
          key++;
        }
      }
    }
    
    Collections.sort(danji);
    
    sb.append(danji.size()).append("\n");
    
    for(int i = 0; i < danji.size(); i++) {
      sb.append(danji.get(i)).append("\n");
    }
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static void check(int x, int y) {
    
    visited[x][y] = true;
    danji.set(key, danji.get(key) + 1);
    
    //상
    if(x > 1) {
      if(map[x-1][y] && !visited[x-1][y]) {
        check(x-1, y);
      }
    }
    //하
    if(x < n) {
      if(map[x+1][y] && !visited[x+1][y]) {
        check(x+1, y);
      }
    }	
    //좌
    if(y > 1) {
      if(map[x][y-1] && !visited[x][y-1]) {
        check(x, y-1);
      }
    }
    //우
    if(y < n) {
      if(map[x][y+1] && !visited[x][y+1]) {
        check(x, y+1);
      }
    }
  }
}

풀이과정

1. DFS 접근으로 재귀함수를 사용하여 풀었다.
2. 숫자를 입력받는 과정에서 StringTokenizer를 사용하였는데, 여기서 에러가 발생하였다.
3. 알아보니 st.nextToken을 하는 과정에서 StringTokenizer는 공백을 기준으로 값을 처리하는데, 입력값이 공백없는 형태여서 제대로 처리가 되지 않았다.
4. 그래서 char 배열로 하여 입력값을 적용하게 되었다.
5. 단지의 수와 단지내 집의 수를 처음에는 분리하여 계산을 하려다가, List를 이용하여 한 번에 계산하는게 좋다고 생각되어 List의 인덱스를 기록하는 key를 만들고,
6. 단지 하나를 돌 때는 같은 key값을 사용하여 list의 값을 변화시켰고, 단지 순회가 끝나면 key를 하나 증가시켜 다음 단지로 넘어가게 하였다.

- 성공
- 메모리 : 14268 KB
- 시간 : 124 ms

보안점

1. StringTokenizer를 토큰화 시키고 값을 하나하나 분리하여 가져올 때 공백이 필요하다는 것을 알게되었다.