[Java]백준 4963번 :: 섬의 개수

백준 온라인 저지 4963번 - 섬의 개수

Java 알고리즘 문제풀이

코딩테스트 DFS, BFS : https://developer-mac.tistory.com/64

풀이

그래프를 이용한 경로탐색 알고리즘에 대표적으로 2가지가 존재한다.

• DFS (깊이 우선 탐색)
• BFS (너비 우선 탐색)

코딩테스트에서 대표적으로 출제되는 문제라 알아두는 것이 좋은 알고리즘인데, 이 문제는 이 두가지 알고리즘을 연습하기에 좋은 문제이다.

실제 코딩테스트에서는 경로를 찾는 문제에서 많이 쓰인다.

 

DFS 알고리즘에 경우 두 가지 방법으로 풀 수 있는데, 

첫 번째로 스택을 이용하는 것

두 번째로 재귀함수를 이용하는 것인데, 재귀함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다.

 

BFS 알고리즘은 Queue를 사용해서 문제를 해결하면 된다.

 

dx, dy로 전역변수로 해둔 배열이 있다. 이 부분은 사각형 기준으로 대각선, 좌우위아래를 다 검사할때 사용하는 배열이다.

경로탐색 알고리즘에 쓰면 좋다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Pairs {
    int x;
    int y;

    Pairs(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Beak4963 {
    static int[][] arr;
    static int[][] check;
    static int[] dx = { 0, 0, 1, -1, 1, -1, 1, -1 };
    static int[] dy = { -1, 1, 0, 0, -1, 1, 1, -1 };

    /* DFS */
    private static void dfs(int x, int y, int count, int w, int h) {
        check[x][y] = count;

        for (int i = 0; i < dx.length; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < h && 0 <= ny && ny < w) {
                if (arr[nx][ny] == 1 && check[nx][ny] == 0)
                    dfs(nx, ny, count, w, h);
            }
        }
    }

    /* BFS */
    private static void bfs(int x, int y, int count, int w, int h) {
        Queue<Pairs> queue = new LinkedList<Pairs>();
        queue.add(new Pairs(x, y));
        check[x][y] = count;
        while (!queue.isEmpty()) {
            Pairs p = queue.remove();
            x = p.x;
            y = p.y;
            for (int i = 0; i < dx.length; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < h && 0 <= ny && ny < w) {
                    if (arr[nx][ny] == 1 && check[nx][ny] == 0)
                        bfs(nx, ny, count, w, h);
                }
            }
        }
    }

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

        while (true) {
            int w = sc.nextInt();
            int h = sc.nextInt();

            if (w == 0 && h == 0)
                break;

            arr = new int[h][w];

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }

            int count = 0;
            check = new int[h][w];

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (arr[i][j] == 1 && check[i][j] == 0)
                        // dfs(i, j, ++count, w, h);
                        bfs(i, j, ++count, w, h);
                }
            }
            System.out.println(count);
        }

        sc.close();
    }
}