[BOJ] 4963. 섬의 개수 - DFS

[BOJ] 4963. 섬의 개수 - DFS

제출일 : 2019-10-07

문제 풀이 시간 : 10M

난이도 : ★

Problem

link : https://www.acmicpc.net/problem/4963

Input

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

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

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

Output

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

Example

input

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

output

0
1
1
3
1
9

Solution & Inpression

DFS의 가장 기본적인 문제

Code

언어 : JAVA

메모리 : 33,252 kb

실행시간 : 312 ms

import java.io.*;
import java.util.*;

public class Main_백준_4963_섬의개수_DFS {
    static int W, H;
    static int[][] map;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        while (true) {
            W = sc.nextInt();
            H = sc.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++) {
                    int tmp = sc.nextInt();
                    if (tmp == 1)
                        map[i][j] = -1;
                    else
                        map[i][j] = tmp;
                }
            }

            int cnt = 0;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (map[i][j] == -1) {
                        map[i][j] = ++cnt;
                        solve(i, j, cnt);
                    }
                }
            }
            System.out.println(cnt);

            // for (int[] is : map)
            // System.out.println(Arrays.toString(is));

        } // end of tc
        sc.close();
    }// end of main

    private static void solve(int i, int j, int cnt) {
        int[] dr = { -1, 1, 0, 0, 1, 1, -1, -1 };
        int[] dc = { 0, 0, -1, 1, 1, -1, -1, 1 };

        for (int k = 0; k < 8; k++) {
            int r = i + dr[k];
            int c = j + dc[k];
            if (range(r, c)) {
                if (map[r][c] == -1) {
                    map[r][c] = cnt;
                    solve(r, c, cnt);
                }
            }
        }
    }

    private static boolean range(int r, int c) {
        if (0 <= r && r < H && 0 <= c && c < W)
            return true;
        return false;
    }
}