[코테] 백준 4963 섬의 갯수: DFS Java

백준은 입력 받는게 너무 부담스럽다....

 

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

 

1) 입력 부분

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

public class baekjoon_4963 {

    static int count; // 섬의 갯수
    static boolean[] visited;

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

        int w = Integer.parseInt(st.nextToken()); // 지도의 너비
        int h = Integer.parseInt(st.nextToken()); // 지도의 높이

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

            st = new StringTokenizer(br.readLine(), " ");
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
        }


        br.close();
    }

}

0 0이 입력되면 테스트 케이스 종료.

첫번째 줄은 지도 가로와 세로 길이, 두번째 줄부터는 지도가 입력됨.

 

2) dfs 함수 로직

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

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

        if (nx >= 0 && ny >= 0 && ny < map.length && nx < map[0].length) {
            if (!visited[ny][nx] && map[ny][nx] == 1) {
                dfs(nx, ny, map);
            }
        }
    }
}

기본적으로 전에 풀었던 dfs 문제들과 동일하다.

그런데 이번엔 '대각선'도 포함이므로 8방향을 사용한다.

dfs에 들어가면 해당 좌표는 방문 처리를 한다.

그리고 8방향을 돌면서, 인접하는 섬에 방문을 한다.

 

전체 코드

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

public class baekjoon_4963 {

    static boolean[][] visited;
    static int[] dx = { 0, -1, 0, 1, -1, -1, 1, 1 }; // 8방향
    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());
            int w = Integer.parseInt(st.nextToken()); // 지도의 너비
            int h = Integer.parseInt(st.nextToken()); // 지도의 높이

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

            int[][] map = new int[h][w];
            visited = new boolean[h][w];

            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());
                }
            }

            int count = 0;
            for (int y = 0; y < h; y++) { // 세로 길이만큼
                for (int x = 0; x < w; x++) { // 가로 길이만큼
                    if (map[y][x] == 1 && !visited[y][x]) { // 방문 안 한 섬이라면
                        dfs(x, y, map);
                        count++;
                    }
                }
            }

            System.out.println(count);
        }

        br.close();
    }

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

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

            if (nx >= 0 && ny >= 0 && ny < map.length && nx < map[0].length) {
                if (!visited[ny][nx] && map[ny][nx] == 1) {
                    dfs(nx, ny, map);
                }
            }
        }
    }
}