[백준] 4963번 섬의 개수 BFS/DFS 사용해서 풀기 : Programming Story

1. 문제

1) 링크

www.acmicpc.net/problem/4963

2) 문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

3) 입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

4) 출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

문제의 세부 조건들을 확인하려면 위의 링크에 들어가서 확인해보자.

2. 풀이

참고로 이 문제는

https://www.programmingstory.com/2024/02/2667.html

위의 문제와 굉장히 유사하니 위의 문제를 먼저 공부하고 오는 것을 추천한다.

다른 점은 위 문제에서는 위, 아래, 왼쪽, 오른쪽 네 가지 방향으로만 움직일 수 있었는데 이 섬 문제의 경우, 대각선으로 움직이는 것도 포함하는 것이다.

따라서,

배열 부분이

public static final int[] dx={1,-1,0,0,1,-1,-1,1};
public static final int[] dy={0,0,1,-1,1,-1,1,-1 };

위와 같이 추가되게 된다.

이 문제도 DFS를 활용해서 구현을 해 보았는데 DFS 함수의 코드만 우선 보자면,

 public static void dfs(int x, int y, int cnt){
        group[x][y]=cnt;
        for(int i=0; i<8; i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if (nx>=0 && ny>=0 && nx<n&& ny<m){
                if (a[nx][ny]==1&&group[nx][ny]==0){
                    dfs(nx, ny, cnt);
                }
            }
        }
    }

위와 같이 쓸 수 있다. 대각선까지 이동할 수 있기 때문에 총 이동할 수 있는 방법이 8개나 된다. 따라서 이번에는 for문을 8번 돌았다.

나머지 알고리즘은 모두 위의 단지번호붙이기 (백준 2667번)과 유사하니 전체 코드만 첨부해보겠다.

import java.util.*;

public class Main{
    public static int [][]a;
    public static int [][]group;
    public static int n;
    public static int m;
    public static final int[] dx={1,-1,0,0,1,-1,-1,1};
    public static final int[] dy={0,0,1,-1,1,-1,1,-1 };
    public static void dfs(int x, int y, int cnt){
        group[x][y]=cnt;
        for(int i=0; i<8; i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if (nx>=0 && ny>=0 && nx<n&& ny<m){
                if (a[nx][ny]==1&&group[nx][ny]==0){
                    dfs(nx, ny, cnt);
                }
            }
        }
    }
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        while(true){
            m=sc.nextInt();
          n=sc.nextInt();
            if (n==0 && m==0){
                break;
            }
            a=new int [n][m];
            group=new int [n][m];
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    a[i][j]=sc.nextInt();
                }
            }
            int cnt=0;
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if (a[i][j]==1 && group[i][j]==0){
                        dfs(i,j, ++cnt);
                    }
                }
            }
            System.out.println(cnt);
        }
      
        
    }
}