[백준 2667/실버1] 단지 번호 붙이기 (자바)

DFS 

 

1. visited 배열 사용하여 정석으로 풀이

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

class Main {
    final static int MAX = 25 + 10;
    static boolean[][] graph;
    static boolean[][] visited;
    static int countPerDanji;
    static int dirY[] = {1, -1, 0, 0};
    static int dirX[] = {0, 0, 1, -1}; // 두 배열 합쳐서 상하좌우
    
    static void dfs(int y, int x) {
        visited[y][x] = true;
        countPerDanji++;
        
        // 상하좌우 갈 수 있는지 확인
        for(int i=0; i<4; i++){
            int newY = y + dirY[i];
            int newX = x + dirX[i];
            if(!visited[newY][newX] && graph[newY][newX]){
                dfs(newY,newX);
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        // 0. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // N * N 크기의 정사각형
             
        graph = new boolean[MAX][MAX];
        visited = new boolean[MAX][MAX];
        
        for(int i=1; i<=N; i++) {
            String s = br.readLine();
            for(int j=1; j<=N; j++) {
                graph[i][j] = s.charAt(j-1) == '1';
            }
        }
        
        // 1. (1,1) 부터 (N,N)까지 돌면서 dfs
        // 각 단지가 몇 개의 아파트로 구성되어 있는지 저장
        ArrayList<Integer> countList = new ArrayList<>();
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if(graph[i][j] && !visited[i][j]) {
                    countPerDanji = 0;
                    dfs(i, j); // 그래프 탐색
                    countList.add(countPerDanji);
                }
            }
        }
        // 2. 출력
        System.out.println(countList.size()); // 총 단지 수
        Collections.sort(countList);
        for(int i=0 ; i<countList.size(); i++){
            System.out.println(countList.get(i));
        }
        
        br.close();
    }   
}

 

2.  graph 배열만 사용하여 풀이

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

// graph 배열만 활용 
class Main {
    final static int MAX = 25 + 10;
    static boolean[][] graph;
    static int countPerDanji;
    static int dirY[] = {1, -1, 0, 0};
    static int dirX[] = {0, 0, 1, -1}; // 두 배열 합쳐서 상하좌우
    
    static void dfs(int y, int x) {
        graph[y][x] = false;
        countPerDanji++;
        
        // 상하좌우 갈 수 있는지 확인
        for(int i=0; i<4; i++){
            int newY = y + dirY[i];
            int newX = x + dirX[i];
            if(graph[newY][newX]){
                dfs(newY,newX);
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        // 0. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // N * N 크기의 정사각형
             
        graph = new boolean[MAX][MAX];
        
        for(int i=1; i<=N; i++) {
            String s = br.readLine();
            for(int j=1; j<=N; j++) {
                graph[i][j] = s.charAt(j-1) == '1';
            }
        }
        
        // 1. (1,1) 부터 (N,N)까지 돌면서 dfs
        // 각 단지가 몇 개의 아파트로 구성되어 있는지 저장
        ArrayList<Integer> countList = new ArrayList<>();
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if(graph[i][j]) {
                    countPerDanji = 0;
                    dfs(i, j); // 그래프 탐색
                    countList.add(countPerDanji);
                }
            }
        }
        // 2. 출력
        System.out.println(countList.size()); // 총 단지 수
        Collections.sort(countList);
        for(int i=0 ; i<countList.size(); i++){
            System.out.println(countList.get(i));
        }
        
        br.close();
    }   
}

 

참고 : 개발자로 취직하기 티스토리 및 유튜브