백준-4963번/섬의 개수(java)

 

 

문제 이해

 

이 문제는 2667번 단지번호붙히기 문제와 매우 유사한 문제라는 생각을 했다.

https://www.acmicpc.net/problem/2667

 

하지만 차이점도 존재했는데, 단지번호 붙히기 문제는 위아래,좌우 로만 이동이 가능했지만 이번 문제는 대각선 이동도 고려해줘야 했다.

 

 

문제 풀이

 

대각선 이동을 위해 정적 변수로 배열 dx, dy를 선언해주었다.

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

 

 

그리고 지도를 돌면서 dfs(깊이우선탐색)을 수행해줌으로써 연결성분을 구할 수 있다.

for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
        if(Map[i][j]==1) {
            dfs(i, j);
            Land++;
        }
    }
}

 

 

 

<dfs 함수>

public static void dfs(int x, int y){
    Map[x][y]=0;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            int nx=x+dx[i];
            int ny=y+dy[j];

            if(nx>=0 && nx<H && ny>=0 && ny<W && Map[nx][ny]==1){
                dfs(nx,ny);
            }
        }
    }
}

 

상하 좌우 대각선 이동을 구현하기 위해 dx dy배열을 반복문을 돌면서 기존의 좌표값에 더해주었다.

 

 

<전체 코드>

import java.util.Scanner;

public class Problem4963 {
    static int Land=0;
    static int[][] Map;
    static int W,H;
    static int[] dx={-1,0,1};
    static int[] dy={-1,0,1};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(true){
            W=scanner.nextInt();
            H=scanner.nextInt();

            if(W==0 && H==0){
                break;
            }

            Map=new int[H][W];
            for(int i=0; i<H; i++){
                for(int j=0; j<W; j++){
                    Map[i][j]=scanner.nextInt();
                }
            }

            for(int i=0; i<H; i++){
                for(int j=0; j<W; j++){
                    if(Map[i][j]==1) {
                        dfs(i, j);
                        Land++;
                    }
                }
            }

            System.out.println(Land);
            Land=0;


        }
    }
    public static void dfs(int x, int y){
        Map[x][y]=0;
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                int nx=x+dx[i];
                int ny=y+dy[j];

                if(nx>=0 && nx<H && ny>=0 && ny<W && Map[nx][ny]==1){
                    dfs(nx,ny);
                }
            }
        }
    }
}