[코드트리] 연결된 칸 찾기 (DFS) - JAVA

알고리즘 스터디 - DFS

https://www.codetree.ai/training-field/search/problems/find-linked-cells/description?page=1&pageSize=20&tags=DFS&order=tier

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

# 문제 

 

# 예제

입력 

7
0 1 1 0 1 0 0
0 1 1 0 1 0 1
1 1 1 0 1 0 1
0 0 0 0 1 1 1
0 1 0 0 0 0 0
0 1 1 1 1 1 0
0 1 1 1 0 0 0

 

출력

3
7
8
9

 

# 필요개념

 

이 문제는 이차원 배열에서 어떤 칸의 위 아래 왼 오른쪽에 있는 칸과 연결이 되어있다고 하는 문제이다. 그래서 리스트배열을 생성하지 않고 이차원 배열을 그대로 사용하기로 했다.

 

대신 dfs를 구현할 때, 신경써줘야 하는 부분이 있는데, 각 배열의 가장자리에 위치할 때 예외처리를 해주어야 한다.

예를 들어 [0][1] 자리에 있다면, 윗 칸에는 아무것도 존재할 수 없고 잘못하면 IndexOutOfBoundsException 에러가 발생할 수 있기 때문에 신경써주어야 한다.

 

main에서는 for문을 돌리면서 방문을 하지 않았으면서 값이 1인 칸에서 dfs를 수행해준다. 한 칸에서 dfs를 수행하면서 한번 dfs를 할 떄마다 카운트를 하여 개수를 세고, 끝나면 리스트에 담아두었다.

 

마지막으로 리스트를 오름차순 정렬해주고 StringBuilder에 담아 출력해준다.

 

# Code

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

public class Main {

    static int n;
    static int cnt;
    static int[][] mainArr;
    static boolean[][] isVisit;

    public static void main(String[] args) throws IOException {
        // 여기에 코드를 작성해주세요.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        StringTokenizer st;
        mainArr = new int[n][n];
        isVisit = new boolean[n][n];
        
        for (int i = 0 ; i < n ; i++) { // 배열에 값 넣기
            st = new StringTokenizer(br.readLine());
            for (int j = 0 ; j < n ; j++) {
                mainArr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        List<Integer> lst = new ArrayList<>();
        for (int i = 0 ; i < n ; i++) {
            for (int j = 0 ; j < n ; j++) {
                cnt = 0;
                if (!isVisit[i][j] && mainArr[i][j] == 1) {
                    int count = dfs(i, j);
                    lst.add(count);
                }
            }
        }        
        Collections.sort(lst);
        StringBuilder sb = new StringBuilder();
        sb.append(lst.size()).append("\n");

        for (int i = 0 ; i < lst.size() ; i++) {
            sb.append(lst.get(i)).append("\n");
        }

        System.out.println(sb.toString());
    }

    public static int dfs(int r, int c) {
        isVisit[r][c] = true;
        cnt++;

        if (r != 0 && (!isVisit[r - 1][c]) && mainArr[r - 1][c] == 1) { // 위
            dfs(r - 1, c);
        } 
        if (r != n - 1 && (!isVisit[r + 1][c]) && mainArr[r + 1][c] == 1) { // 아래
            dfs(r + 1, c);
        } 
        if (c != 0 && (!isVisit[r][c - 1]) && mainArr[r][c - 1] == 1) { // 왼
            dfs(r, c - 1);
        } 
        if (c != n - 1 && (!isVisit[r][c + 1]) && mainArr[r][c + 1] == 1) { // 오
            dfs(r, c + 1);
        } 

        return cnt;

    }
}

 

# 결과