[백준](Java) 4963 - 섬의 개수

민지킴·2021년 5월 31일
0

백준

목록 보기
22/48
post-thumbnail

문제 링크

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

문제 풀이

평범한 bfs 문제였다. 다만 기존에는 4방향으로 가던걸 8방향으로 바꿔준것에 차이가 있었다.


코드

import java.util.*;

public class Main {

    static int n;
    static int m;
    static int[][] map;
    static boolean[][] chk;
    static int answer = 0;
    //12시 방향부터 시계방
    static int[] diry = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dirx = {0, 1, 1, 1, 0, -1, -1, -1};

    static class Node {
        int y;
        int x;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            n = sc.nextInt();
            m = sc.nextInt();
            if (n == 0 && m == 0) {
                //종료조건
                break;
            }
            map = new int[m][n];
            chk = new boolean[m][n];
            answer = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    map[i][j] = sc.nextInt();
                }
            }

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (!chk[i][j] && map[i][j] == 1) {
                        dfs(i, j);
                    }
                }
            }
            System.out.println(answer);
        }

    }

    public static void dfs(int y, int x) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(y, x));
        chk[y][x] = true;
        answer++;
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            for (int i = 0; i < 8; i++) {
                int now_y = now.y + diry[i];
                int now_x = now.x + dirx[i];
                if (now_y >= 0 && now_y < m && now_x >= 0 && now_x < n) {
                    if (!chk[now_y][now_x] && map[now_y][now_x] == 1) {
                        queue.add(new Node(now_y, now_x));
                        chk[now_y][now_x] = true;
                    }
                }
            }

        }

    }
}

profile
하루하루는 성실하게 인생 전체는 되는대로

0개의 댓글