[99클럽 코테 스터디 6일차 TIL] 섬의 개수 ( 그래프 )

오늘의 키워드 

• 그래프 이론 
• 그래프 탐색 
• 깊이 우선 탐색 
• 너비 우선 탐색 

문제 파악 

지난번 4일차에 풀었던 배경화면 정리하기 문제와 거의 유사한 문제이다. 

하나의 노드를 탐색할때, 지난 문제에서는 대각선을 제외한 위치를 인접 노드라고 인식했다면, 

이번에는 하나의 격자를 둘러썬 모든 격자를 인접 노드로 보면 된다. 

 

문제 해결 방법 

1. 입력으로 w(너비), h(높이)와 땅/바다 정보가 주어진다.
2. 이중 for문으로 전체 지도를 순회하며, 땅(1)을 발견하면 dfs() 함수를 호출해 인접한 모든 땅을 탐색하고, 방문 처리를 해준다.
3. 하나의 DFS 탐색이 끝났다는 것은 하나의 섬을 다 방문한 것이므로 cnt++로 섬의 개수를 증가시킨다.
4. 방향 벡터를 8방향(상, 하, 좌, 우, 대각선 포함)으로 설정하여, 대각선으로 연결된 땅도 같은 섬으로 처리했다.

import java.awt.print.Pageable;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
    public static int[][] heights;
    public static int cnt = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            String readLine = br.readLine();
            // w, h 입력받기
            String[] readLine_split = readLine.split(" ");
            int w = Integer.parseInt(readLine_split[0]);
            int h = Integer.parseInt(readLine_split[1]);

            // 입력 종료
            if (w==0 && h ==0){
                break;
            }

            // 육지와 바다 정보 입력받기
            int[][] earth = new int[h][w];
            for(int i=0; i<h; i++){
                readLine = br.readLine();
                String[] row = readLine.split(" ");
                for(int j=0; j<w; j++){
                    earth[i][j] = Integer.parseInt(row[j]);
                }
            }

            int cnt = 0;
            for(int i=0; i<h; i++){
                for(int j=0; j<w; j++){
                    // 1은 땅, 0은 바다
                    if(earth[i][j] == 1) {
                        dfs(earth,i,j);
                        cnt += 1 ;
                    }
                }
            }
            System.out.println(cnt);
        }
    }

    public static void dfs(int[][] earth, int i, int j){
        // exit 조건
        if (earth[i][j] == 0 ) return;

        // 방문 표시
        earth[i][j] = 0;
        int[] dx = {-1,0,1,1,1,0,-1,-1};
        int[] dy = {-1,-1,-1,0,1,1,1,0};

        for (int k=0; k<8; k++) {
            int next_i = i+dy[k]; int next_j = j+dx[k];
            if (next_i >= 0 && next_i< earth.length && next_j >=0 && next_j < earth[0].length )
                dfs(earth,i+dy[k], j+dx[k]);
        }
    }
}

 

 

💡 회고 

DFS는 많이 풀어봤지만, 이렇게 입력부터 다 직접 처리해야 하는 문제를 풀어보는 게 실전 감각을 기르는 데 도움이 많이 되었다. 특히 8방향 탐색을 하며 지난번에 풀었던 문제를 다시 복기할 수 있었다.  다음에는 BFS 방식으로도 한번 풀어보고, 섬 크기까지 함께 구하는 확장 문제도 도전해보고 싶다. 섬크기를 구하려면 dfs 함수 외부가 아니라 내부에서 방문과 동시에 area +=1 처리를 하면 될 것 같다. 

 

또한 8방향을 방문하기 위해 배열에 미리 dx, dy 를 정리하여 더함으로써 더 직관적으로 문제를 풀 수 있었다.