[백준][2667번] 단지번호붙이기

문제 URL

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

나의 풀이

(1) dfs를 이용해서 지도 전체를 순회하며 연결요소를 구하면된다. (2) 인접리스트, 인접행렬 만들필요없다. 단지 각 단계마다 위,아래,왼쪽,오른쪽 가는 경우를 구현하면된다.

package backjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static int[][] map;
    static boolean[][] check;
    static int n;

    public static void main(String args[]) throws IOException {
        n = Integer.parseInt(bf.readLine());
        map = new int[n][n];
        check = new boolean[n][n];
        ArrayList<Integer> num = new ArrayList<>();

        for(int i=0; i<n; i++){
            String str= bf.readLine();
            for(int j=0; j<n; j++){
                map[i][j] = Character.getNumericValue(str.charAt(j));
            }
        }

        int answer = 0; //연결요소 수
        //(1)
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(check[i][j] || map[i][j] != 1)
                    continue;
                answer++;
                int m = dfs(i,j);
                num.add(m);
            }
        }
        //결과출력을 위한 정렬
        Collections.sort(num);
        System.out.println(answer);
        for(int i=0; i<answer; i++){
            System.out.println(num.get(i));
        }
    }

    public static int dfs(int x, int y) {
        check[x][y] = true;
        int answer=1;

        //오른쪽으로 가는 경우
        if((x+1)<n && map[x+1][y] == 1 && !check[x+1][y]){
            answer += dfs(x+1,y);
        }
        //ㅏ왼쪽으로 가는 경우
        if(0<=(x-1) && map[x-1][y] == 1 && !check[x-1][y]){
            answer += dfs(x-1,y);
        }
        // 위로 가는 경우
        if((y+1)<n && map[x][y+1] == 1 && !check[x][y+1]){
            answer += dfs(x,y+1);
        }
        //아래로 가는경우
        if (0<=(y-1) && map[x][y-1] == 1 && !check[x][y-1]){
            answer += dfs(x,y-1);
        }
        return answer;
    }
}