알고리즘 풀이 - 백준 4963(섬의 개수, 그래프(DFS, BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

지도에 섬, 바다가 표시되어 있을 때, 섬의 개수를 구하는 문제. 같은 섬의 기준은 상하좌우대각선으로 연결된 경우

 

 

2. 풀이

 

h x w 크기의 지도가 주어질 때, 1로 표시된 곳은 섬이고 0으로 표시된 곳은 바다이다. 그러므로 현재 탐색 위치의 인접한 섬을 모두 찾아낸다면 그것이 하나의 큰 섬이 된다.

인접한 섬을 찾아낼 수 있는 자료구조는 그래프이다. 인접 행렬로 지도를 저장하고 각각의 위치에서 탐색을 시작하여 이어진 섬 전체의 개수를 찾아내면 된다.

 

그래프를 탐색해야 하므로 DFS, BFS의 구조를 통해 탐색을 수행하자.

탐색을 수행할 때는 인접한 모든 곳을 다시 탐색해서는 안되므로 방문 완료 여부를 저장해야 한다. 이를 통해 탐색이 정상적으로 수행될 수 있도록 구현해보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① DFS로 구현하기

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main{
    static int[][] map;
    static boolean[][] visited;
    
    // 각각 상, 하, 좌, 우, 좌상, 우상, 좌하, 우하
    static int[] dy = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int[] dx = {0, 0, -1, 1, -1, 1, -1, 1};
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();

        while(true){
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            
            // 마지막에 둘 다 0만 주어지면 반복문 탈출
            if(w == 0 && h == 0) break;
            
            // 지도를 초기화
            map = new int[h][w];
            visited = new boolean[h][w];
            
            for(int i=0; i < h; i++){
                st = new StringTokenizer(br.readLine());
                for(int j=0; j < w; j++){
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            // 각 위치에서 탐색 시작하여 섬의 개수를 찾는다.
            int island = 0;
            for(int i=0; i < h; i++){
                for(int j=0; j < w; j++){
                    // 방문 완료되었거나 섬이 아닌 바다 부분이면 다음으로 넘어간다.
                    if(visited[i][j] || map[i][j] == 0) continue;
                    dfs(i, j, h, w);
                    
                    // dfs가 동작했다면 하나의 섬을 찾은 것
                    island++;
                }
            }
            sb.append(island).append("\n");
        }
        
        System.out.println(sb);
        br.close();
    }

    // DFS를 통해 섬을 찾아낸다.
    private static void dfs(int i, int j, int h, int w){
    
        // 탐색한 정점은 방문 완료 표시
        visited[i][j] = true;
        
        for(int k=0; k < 8; k++){
            int ny = i + dy[k];
            int nx = j + dx[k];
            
            // 범위를 벗어나거나 기 방문 됐거나 섬이 아니면 넘어간다.
            if(ny < 0 || ny >= h || nx < 0 || nx >= w || visited[ny][nx] || map[i][j] == 0) continue;
            dfs(ny, nx, h, w);
        }
    }
}

 

② BFS로 구현하기

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

public class Main{
    static int[][] map;
    static boolean[][] visited;
    static int w;
    static int h;

    // 각각 상, 하, 좌, 우, 좌상, 우상, 좌하, 우하
    static int[] dy = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int[] dx = {0, 0, -1, 1, -1, 1, -1, 1};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();

        while(true){
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            // 마지막에 둘 다 0만 주어지면 반복문 탈출
            if(w == 0 && h == 0) break;

            // 지도를 초기화
            map = new int[h][w];
            visited = new boolean[h][w];

            for(int i=0; i < h; i++){
                st = new StringTokenizer(br.readLine());
                for(int j=0; j < w; j++){
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            // 각 위치에서 탐색 시작하여 섬의 개수를 찾는다.
            int island = 0;
            for(int i=0; i < h; i++){
                for(int j=0; j < w; j++){
                    // 방문 완료되었거나 섬이 아닌 바다 부분이면 다음으로 넘어간다.
                    if(visited[i][j] || map[i][j] == 0) continue;
                    bfs(i, j);

                    // bfs가 동작했다면 하나의 섬을 찾은 것
                    island++;
                }
            }
            sb.append(island).append("\n");
        }

        System.out.println(sb);
        br.close();
    }

    // BFS를 통해 섬을 찾아낸다.
    private static void bfs(int i, int j){
        Queue<Map> q = new LinkedList<>();

        // 탐색 시작 정점은 Queue에 넣고 방문 완료 표시
        q.offer(new Map(i, j));
        visited[i][j] = true;

        while(!q.isEmpty()){
            Map now = q.poll();

            for(int k=0; k < 8; k++){
                int ny = now.y + dy[k];
                int nx = now.x + dx[k];

                // 다음 탐색 위치가 범위를 벗어나거나 기 방문 됐거나 섬이 아니면 넘어간다.
                if(ny < 0 || ny >= h || nx < 0 || nx >= w || visited[ny][nx] || map[ny][nx] == 0) continue;

                visited[ny][nx] = true;
                q.offer(new Map(ny, nx));
            }
        }
    }
}

class Map{
    int y;
    int x;
    public Map(int y, int x){
        this.y=y;
        this.x=x;
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.