백준 Java_2667

• DFS가 아무래도 재귀의 방법을 사용하다 보니 static, 정적 변수를 사용할 일이 많다.

단지 번호를 붙일 때, dirX 좌 우를 판단, dirY 상 하의 범위를 판단

• 왼쪽으로 가려면 기준점에서 -1을 해야되고 오른쪽으로 가려면 +1을 한다.
• nowX와 nowY는 범위를 계산한 좌표를 담을 변수
• DFS()는 연결된 1을 따라서만 쭉 가기 때문에 모든 면에 0이 있으면 더 이상 갈 수 없다고 판단해서 메소드가 종료된다. 그렇기 때문에 전체 배열을 탐색하면서, 방문하지 않았고, arr에서 1인 곳을 만날경우 다시 DFS() 메소드가 실행되도록 하면 arr 전체를 탐색할 수 있다.
• arr이 1이면서 방문하지 않은 곳일 경우 실행되어실행되는 순간 방문함을 표시하기 위해 visit[x][y] = true 처리를 해주고 단지번호 부여를 위해 arr[x][y] = number;를 넣어준다.
• Range_check() 메소드를 실행해서 범위조건에 true일 경우에만,방문 여부를 true로 바꿔주고, 다시 단지번호를 부여

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

public class Main {
    static int arr[][];
    static boolean visit[][];
    static int dirX[] = {0, 0, -1, 1};
    static int dirY[] = {-1, 1, 0, 0};

    static int count = 0, number =0;
    static int nowX, nowY, N ;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        List<Integer> list = new ArrayList<>();
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        visit = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String str = br.readLine();

            for (int j = 0; j < N; j++) {
                arr[i][j] = Character.getNumericValue(str.charAt(j));
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visit[i][j] == false && arr[i][j] == 1) {
                    count = 0;
                    number++;
                    DFS(i, j);
                    list.add(count);
                }
            }
            }

        Collections.sort(list);
        bw.append(number + "\n");
        for (int num : list) {
            bw.append(num + "\n");
        }
        bw.flush();
        bw.close();
    }

    static void DFS(int x, int y) {
        visit[x][y] =true;
        arr[x][y] = number;
        count++;

        for (int i = 0; i < 4; i++) {
            nowX = dirX[i] +x;
            nowY = dirY[i] + y;

            if (check() && visit[nowX][nowY] == false && arr[nowX][nowY] == 1) {
                visit[nowX][nowY] = true;
                arr[nowX][nowY]  = number;
                DFS(nowX, nowY);
            }
        }
    }

    static boolean check() {
        return (nowX >= 0 && nowX < N && nowY >=0 && nowY < N);
    }

}

참조 : https://velog.io/@lifeisbeautiful/Java-백준-2667번-단지번호붙이기-자바