(#4963 Java) 섬의 개수

 

 문제 이해

 

건너갈 수 있는 경로가 있으면 같은 섬에 있다고 보고, 섬의 개수를 세는 문제이다. 이 문제는 dfs/bfs 문제로 풀 수 있다.

따로 테스트 케이스가 몇 개인지 주어지지 않고,  w,h로 0이 주어지면 프로그램이 종료되므로, 0을 2개 입력 받기 전까지 반복해주면 된다. 그럼 문제를 해결해보자.

 

문제 해결

 

우선 내가 처음부터 생각하지 못했던 부분은 대각선도 이동할 수 있다는 부분이다. 상하좌우까지만 좌표설정을 해보았는데, 대각선은 처음이다.

대각선 이동은 (상+좌), (상+우), (하+좌), (하+우)의 네 가지 경우가 있으므로 아래와 같이 설정하면 된다.

 

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

 

그럼 평소 dfs 문제를 풀던 것처럼 static 변수 설정을 해준다.

여기에서 내가 계속 문제를 틀렸던 부분이 있는데, 바로 w, h 부분이다. 

당연히 입력 순서로 아무 생각없이 배열을 [w][h] 이렇게 선언했는데, 높이 h가 행의 개수, 너비 w가 열의 개수임을 주의하고 가야한다. 이것때문데 배열 설정도 잘못하고 반복문도 행과 열을 반대로 돌려 계속 답이 안 나왔었다.

static int w, h; //높이 h가 행의 개수, 넓이 w가 열의 개수임. 주의!!!
static int[][] Graph;
static boolean[][] Visited;
static int count;
static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1}; //좌우 + 대각선
static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1}; //상하 + 대각선

 

 

그리고 나머지 dfs 함수는 동일하게 작성해주면 된다. 대각선 포함이니 반복을 8번하는 것으로 설정해주는 것만 주의하면 된다.

public static void dfs(int x, int y) {
    Visited[x][y] = true;

    for (int i = 0; i < 8; i++) { //대각선까지 총 8번 반복
        int nr = x + dx[i];
        int nc = y + dy[i];

        if (nr < 0 || nr > h - 1 || nc < 0 || nc > w - 1)
            continue;
        if (Visited[nr][nc])
            continue;
        if (Graph[nr][nc] != 1)
            continue;
        dfs(nr, nc);
    }
}

 

 

main도 동일하다. 위에서 언급한 행과 열에만 주의하면서 작성해준다.

여기에서는 테스트케이스 수가 나와있지 않고, w,h에 둘 다 0이 입력되면 종료된다고 했으니, 둘 다 0이 입력되었을 때 반복문을 빠져나가게 하자. 

 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        //테스트 케이스가 따로 주어지지 않음. 0 0 을 입력 받을 때까지 반복.
        while (true) {

            w = in.nextInt();
            h = in.nextInt();
            Graph = new int[h + 1][w + 1]; //행,열 헷갈리지 말기..!(h:행의 수/ w:열의 수)
            Visited = new boolean[h + 1][w + 1];
            count = 0;

            if (w == 0 && h == 0) //w,h 둘 다 0 입력 시 반복문 빠져나감.
                break;

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    Graph[i][j] = in.nextInt();
                }
            }
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (!Visited[i][j] && Graph[i][j] == 1) { //방문하지 않았고, 섬이 있으면 dfs 호출 & count 증가
                        dfs(i, j);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }
}

 

 

최종 코드

 

package org.example.DfsBfs;

import java.util.Scanner;

public class NumberOfIslands {

    static int w, h; //높이 h가 행의 개수, 넓이 w가 열의 개수임. 주의!!!
    static int[][] Graph;
    static boolean[][] Visited;
    static int count;
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1}; //좌우 + 대각선
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1}; //상하 + 대각선

    public static void dfs(int x, int y) {
        Visited[x][y] = true;

        for (int i = 0; i < 8; i++) { //대각선까지 총 8번 반복
            int nr = x + dx[i];
            int nc = y + dy[i];

            if (nr < 0 || nr > h - 1 || nc < 0 || nc > w - 1)
                continue;
            if (Visited[nr][nc])
                continue;
            if (Graph[nr][nc] != 1)
                continue;
            dfs(nr, nc);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        //테스트 케이스가 따로 주어지지 않음. 0 0 을 입력 받을 때까지 반복.
        while (true) {

            w = in.nextInt();
            h = in.nextInt();
            Graph = new int[h + 1][w + 1]; //행,열 헷갈리지 말기..!(h:행의 수/ w:열의 수)
            Visited = new boolean[h + 1][w + 1];
            count = 0;

            if (w == 0 && h == 0) //w,h 둘 다 0 입력 시 반복문 빠져나감.
                break;

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    Graph[i][j] = in.nextInt();
                }
            }
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (!Visited[i][j] && Graph[i][j] == 1) { //방문하지 않았고, 섬이 있으면 dfs 호출 & count 증가
                        dfs(i, j);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }
}