[탐색알고리즘] DFS

halfstorage.tistory.com/84

[탐색알고리즘] 깊이 우선 탐색, 너비 우선 탐색

이전에 포스팅 했던 탐색알고리즘 중 깊이 우선 탐색 알고리즘에 대해 포스팅하려고합니다.

 

우선 알고리즘 문제는 NHN 채용사이트에서 공개된 Pre-Test 문제를 참고했습니다.

문제가 된다면 다른 알고리즘 문제로 대체하도록 하겠습니다.

문제출처: https://recruit.nhn.com/pdf/%ED%94%84%EB%A6%AC%ED%85%8C%EC%8A%A4%ED%8A%B8_1%EC%B0%A8_%EA%B8%B0%EC%B6%9C%EB%AC%B8%EC%A0%9C.pdf

 

 

 

public class PreTest {
    static int[] x = {-1, 1, 0, 0};
    static int[] y = {0, 0, -1, 1};
    static int[][] rowCol;
    static int index;
    static int tmp;
    static boolean[][] visitRowCol;
 
    public static void main(String[] args) {
        preOne();
    }
    
    private static void preOne() {
        int cnt = 0;
        List<Integer> resList = new ArrayList<>();
        
        Scanner sc = new Scanner(System.in);
        index = sc.nextInt();
        
        rowCol = new int[index][index];
        visitRowCol = new boolean[index][index];
        
        for(int i=0; i<index; i++) {
            for(int j=0; j<index; j++) {
                rowCol[i][j] = sc.nextInt();
            }
        }
        
        for(int i=0; i<index; i++) {
            for(int j=0; j<index; j++) {
                if(rowCol[i][j] == 1 && !visitRowCol[i][j]) {
                    tmp = 1;
                    dfs(i, j);
                    cnt++;
                    resList.add(tmp);
                }
            }
        }
        System.out.println(cnt);
 
        Collections.sort(resList);
        for(int i: resList) {
            System.out.print(i + " ");
        }
    }
    
    private static void dfs(int row, int col) {
        visitRowCol[row][col] = true;
        for(int i=0; i<4; i++) {
            if( row + x[i] >= 0 && 
                col + y[i] >= 0 &&
                row + x[i] < index && 
                col + y[i] < index) {
                if( rowCol[row + x[i]][col + y[i]] == 1 && 
                    !visitRowCol[row+x[i]][col+y[i]] ) {
                    tmp++;
                    dfs(row + x[i], col + y[i]);
                }
            }
        }
    }
}