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

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

2667번: 단지번호붙이기

 

제출 날짜: 2021년 9월 20일 월요일

 

 

 

접근 방법

입력을 받을 때 1이라면 -1로 바꿔 map에 저장했다. 그리고 단지 번호를 1부터 차례로 입력을 받았다.

단지 번호 붙이는 건 dfs를 사용했다.

 

 

 

생각

연결된 부분에 숫자를 붙이는 문제인데, 백준저지 다리 만들기 2(https://www.acmicpc.net/problem/17472)를 풀 때 사용해야했던 방법이다.

문제를 풀 때 시간이 많이 걸렸는데 모두 코드를 잘못 입력한 탓이었다. 몇 가지 변수를 static으로 선언을 했는데, 정작 main에서 배열 크기 지정하는 것을 잊어서 java.lang.NullPointerException이 발생했다. 이후에는 dfs로 파라미터를 넘길 때 (i,j)로 넘겼어야 했는데 (0,0)으로 넘겨서 계속 (0,0)에서만 dfs가 발생하는 문제가 생겼다. 마지막으로는 map[dx][dy]가 아닌 map[dx][dx]로 입력하는 바람에 숫자가 이상하게 입력되었다. 첫 번째는 예전에도 반복했던 실수였고, 두 번째까지는 나름 빨리 찾아냈지만 마지막 문제는 찾는데 1시간은 걸린 것 같다. 이런 실수를 줄여야 할 텐데 애초에 입력을 차근차근 제대로 하는 수밖에 없는 것 같다.

 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

public class BOJ2667 {
    static int[][] map;
    static int N, cnt;
    static boolean[][] visited;
    static int[][] d = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            char[] inputChar = (br.readLine()).toCharArray();
            for (int j = 0; j < N; j++) {
                map[i][j] = (inputChar[j] - '0' == 1) ? -1 : 0; // 1은 -1로 바꾸기
            }
        }

        ArrayList<Integer> colorCntArr = new ArrayList<>();
        visited = new boolean[N][N];
        int colorNum = 1; // 단지별 번호
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j] && map[i][j] == -1) {
                    cnt = 0; // 단지수 0으로 초기화
                    colorNumbering(i, j, colorNum); // dfs로 단지별 번호 넣어 칠하기
                    colorCntArr.add(cnt); // 단지수
                    colorNum++;
                }
            }
        }

        Collections.sort(colorCntArr); // 정렬
        bw.write(colorCntArr.size() + "\n");
        for (int i = 0; i < colorCntArr.size(); i++) {
            bw.write(colorCntArr.get(i) + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static void colorNumbering(int x, int y, int colorNum) {
        visited[x][y] = true;
        map[x][y] = colorNum;
        cnt++;

        for (int dd = 0; dd < 4; dd++) {
            int dx = x + d[dd][0];
            int dy = y + d[dd][1];
            if (isInMap(dx, dy) && !visited[dx][dy] && map[dx][dy] == -1) {
                colorNumbering(dx, dy, colorNum);
            }
        }
    }

    private static boolean isInMap(int x, int y) {
        if (x >= 0 && x < N && y >= 0 && y < N) {
            return true;
        }
        return false;
    }

}