백준 2667번: 단지번호붙이기

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

 

저번 문제에 띄어쓰기 없는 입력에 꽤 애먹은 덕분에 이번에는 보다 쉽게 처리할 수 있었다.

한줄 한줄을 일단, String으로 입력받고, str.charAt() - '0'과 같은 형태로 수로 입력받았다.

또한, 내가 언제나 표 형태 그래프 문제를 풀 때 마다 그러하듯

행과 열을 2개 씩 추가하고 그에 맞춰 index값을 조정해주었다.

 

 이번에는 그래프를 ArrayList에 일단 담아두고 그곳에 있는 값을 하나씩 꺼내썼다.

값을 꺼낸 뒤에 해당 그래프와 연결된 그래프를 탐색하고,

탐색한 그래프와 이어진 그래프를 찾고, 배열 내의 값을 변경하는 것으로 방문을 확인했다.

그와 동시에 ArrayList에 남아있는 값도 일종의 방문 처리로서 삭제해주었다.

 

맨 처음에는 출력 조건을 대충 봐서 틀렸던 건데,

각 단지 내 가구 수를 오름차순으로 출력해야한다는 것이다.

그래서 가구 수를 또 다른 ArrayList에 저장하고

나중에 Collections.sort()로 정렬해서 출력해주었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
//import java.util.StringTokenizer;
import java.util.Collections;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));    
    int N = Integer.parseInt(br.readLine());
    ArrayList<Integer> graph = new ArrayList<>();
    //Index => 0 ~ row * col. N ~ N + row *col.

    int[][] tbl = new int[N + 2][N + 2];
    for (int row = 1; row < N + 1; row++) {
      String str = new String(br.readLine());
      for (int col = 1; col < N + 1; col++) {
        tbl[row][col] = str.charAt(col - 1) - '0';
        if (tbl[row][col] == 1) graph.add(row * N + col - 1);
      }
    }

    int block = 0;
    ArrayList<Integer> RES = new ArrayList<>();
    while ( !graph.isEmpty() ) {
      block++;
      Queue<Integer> srchQ = new LinkedList<>();
      int index = graph.remove(0);
      srchQ.offer( index );
      int row = index / N;
      int col = index % N + 1;
      tbl[row][col] = 0;
      int house = 0;

      while ( !srchQ.isEmpty() ) {
        house++;
        index = srchQ.poll();
        row = index / N;
        col = index % N + 1;
        
        if (tbl[row][col + 1] == 1) {
          tbl[row][col + 1] = 0;
          srchQ.offer( index + 1 );
        }
        if (tbl[row][col - 1] == 1) {
          tbl[row][col - 1] = 0;
          srchQ.offer( index - 1 );
        }
        if (tbl[row + 1][col] == 1) {
          tbl[row + 1][col] = 0;
          srchQ.offer( index + N );
        }
        if (tbl[row - 1][col] == 1) {
          tbl[row - 1][col] = 0;
          srchQ.offer( index - N );
        }
        graph.removeAll(srchQ);
      }
      RES.add(house);
    }

    Collections.sort(RES);
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write( block + "\n" );
    for (Integer i : RES) bw.write(i + "\n");
    bw.flush();
    bw.close();
  }
}