백준 4963번 섬의 개수(JAVA) - DFS

백준 4963번

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

4963번: 섬의 개수

 

 

문제설명

섬과 바다 지도가 주어지는데, 섬의 개수를 세는 문제

- 가로, 세로, 대각선으로 연결되어 있으면 걸어갈 수 있다.

- 지도의 너비 w와 h를 입력받는다. (행/렬 구분 주심)

- w,h가 0 0 이 들어오기 전까지 계속 반복하며 0 0 이 들어오면 종료.

 

 

접근

DFS로 접근 (상하좌우, 대각선까지 정의)

 

코드

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

public class Main {
    static int[][] land;
    static int[][] visit;
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    static int h;
    static int w;

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


        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 1 = 땅 , 0 = 바다
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

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

            land = new int[h][w];
            visit = new int[h][w];
            int ans = 0;

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

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (visit[i][j] != 1 && land[i][j] == 1) {
                        dfs(i, j);
                        ans++;
                    }
                }
            }
            System.out.println(ans);
        }

    }

    static void dfs(int x, int y) {
        visit[x][y] = 1;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
            if (land[nx][ny] == 1 && visit[nx][ny] != 1)
                dfs(nx, ny);
        }

    }
}

 

풀이

1. dx, dy를 상하좌우, 대각선 4방향까지 모두 정의

2. w와 h를 입력받는다.

3. 지도(land) 와 방문여부(visit)을  w,h크기만큼 선언 해준다.

4. 지도의 정보를 입력받음

5. 반복문을 돌며 각좌표마다 방문한적이 없고, 땅일 경우 dfs 호출

6. dfs함수는 호출한 좌표를 방문 체크 하고, 자기를 둘러싼 8방향 모두 확인하며 방문하지 않았고, 땅인지 확인후 dfs재귀로 호출