[문제 풀이] 백준 4963번 섬의 개수 JAVA

문제

  문제접근 방법   

해당 문제는 정사각형으로 이루어져 있는 섬과 바다 지도가 주어질 때 섬의 개수를 세는 프로그램을 작성하는 문제로 1은 땅 0은 바다를 의미한다. 

문제를 읽어보면 섬의 개수를 구해야하고 1은 땅 0은 바다를 의미한다는 것을 알 수가 있다.

즉, 1==땅, 연결된 땅 == 섬 이라는 결론을 도출할 수가 있다. 그래서 bfs/dfs를 활용하여 문제를 해결해 보기로 결정하였다.

이중에서도 dfs를 활용하여 코드를 작성하였고 현재 좌표에서 상하좌우대각선 중에서 땅이 존재한다면 해당 좌표로 이동해 상하좌우대각선 탐색하는 식으로 문제를 접근하였다. 

 

< 최종 코드 >

import java.util.*;

public class Main{
    
    public static boolean visited[][];
    public static int island[][];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        StringBuilder sb=new StringBuilder();
        
        while(true){
            int w=s.nextInt();
            int h=s.nextInt();
            int cnt=0;
            if(w==0&&h==0){
                break;
            }
            visited=new boolean[h][w];
            island=new int[h][w];
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    island[i][j]=s.nextInt();
                }
            }
            
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    if(!visited[i][j]&&island[i][j]==1){
                        dfs(i,j);
                        cnt+=1;
                    }
                }
            }
            sb.append(cnt).append("\n");
            
        }
        System.out.print(sb);
    }
    
    public static void dfs(int h,int w){
        if(visited[h][w]||island[h][w]==0){
            return;
        }
        int dh[]={-1,1,0,0,-1,-1,1,1};
        int dw[]={0,0,-1,1,-1,1,-1,1};
        visited[h][w]=true;
        
        
        
        
        for(int i=0;i<8;i++){
            int nh=h+dh[i];
            int nw=w+dw[i];
            if(nh>=0&&nw>=0&&nh<visited.length&&nw<visited[0].length){
                dfs(nh,nw);
            }
            
        }
    }
    
}

 

해당 문제에서 핵심은 연결된 덩어리의 수를 찾는다는라는 점이다 이에 집중해 문제에 접근한다면 쉽게 풀이가 가능하다. 

island 배열에 지도 값을 저장해주고 visited을 통해 방문처리해 주어 중복된 값을 방지해 준다.

dfs가 호출될 때 해당 좌표에 연결된 모든 부분을 탐색하기 때문에 dfs호출 == 섬 1개라고 해석이 가능하다.

그래서 dfs의 호출이 끝날 때마다 cnt를 통해 섬의 개수를 추가해 주었다.

dfs 함수의 전체 흐름은  visited와 island가 조건에 맞지 않는다면 return 해주고 아니라면 

dh, dw를 통해서 상하좌우 대각선이동 처리를 해주면 아래에서 이동좌표에 땅이 있다면 재귀를 통해 처리해 주는 방식이다.

해당 문제는 미로탐색에서 상하좌우 방향만 신경 써야 하는 것에 대각선이라는 조건을 추가해 준 문제다.

만약 문제가 어려웠거나 접근이 쉽지 않았다면 미로탐색문제를 다시 한번 풀어볼 것을 추천한다. 

 

  마무리  

해당 문제는 앞서 풀이했던 미로탐색 문제를 풀이했다면 bfs던지 dfs던지 접근해서 풀이가 가능한 문제라 생각된다.

미로 탐색문제를 완전하게 이해하고 풀이해서 대각선이라는 조건만 염두하고 문제를 풀이했고 쉽게 풀려나던 문제이다.

 

  추가 코드 분석 및 풀이  

위에서는 dfs로 접근해 보았지만 bfs로도 충분히 풀이가 가능하다. 물론 최소 섬의 개수를 구하는 문제는 아니기 때문에 

굳이 풀이할 필요는 없지만 두 알고리즘 다 자주 사용되고 이해하고 있으면 좋다고 판단해 풀이해보려 한다.

< 추가 코드 ver BFS >

- 추후 업데이트 예정