자바(Java) 알고리즘 문제풀이 섬의 갯수 [백준 / DFS]

출처 - 구글 이미지

 

 

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

4963번: 섬의 개수

 

 

풀이 코드

여러가지 테스트 케이스를 자유롭게 입력받아야 하는 부분이 조금 까다로운 문제였다.

대각선을 허용하기 때문에 4방향 벡터가 아닌 8방향 벡터를 사용해서 풀이하면 되는 문제.

int[][] map 이차원 배열과 동일한 크기의 boolean[][] visited 방문 체크 배열을 따로 만들지 않고 map 배열에서 1인 경우 (땅인 경우) 

일 때 바로 카운팅을 해주고, 해당 좌표를 인자로 가진 DFS() 함수를 재귀 호출 하는 방식으로 풀이했다.

package backjoonsliver.dfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class 섬의_개수 {

    static int h;
    static int w;
    static int count = 0;
    static int[][] map;
    static int[] dx = {0, -1, 0, 1, -1, -1, 1, 1};
    static int[] dy = {1, 0, -1, 0, 1, -1, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            map = new int[h][w];

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

            for (int i = 0; i < h; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < w; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (map[i][j] == 1) {
                        count++;
                        DFS(i, j);
                    }
                }
            }

            System.out.println(count);
            count = 0;
        }
    }

    private static void DFS(int x, int y) {
        map[x][y] = 0; // 방문 체크

        for (int i = 0; i < 8; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;

            if (nx >= 0 && ny >= 0 && nx < h && ny < w && map[nx][ny] == 1) {
                map[nx][ny] = 0; // 이동 시 방문 체크
                DFS(nx, ny);
            }
        }
    }
}

// 1 = 땅, 0 = 바다