섬나라(BFS/DFS 기본 로직)_자바

섬나라(BFS/DFS 기본 로직) 

 

BFS와 DFS를 이해할만한 기본 로직이다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//7
//1 1 0 0 0 1 0
//0 1 1 0 1 1 0
//0 1 0 0 0 0 0
//0 0 0 1 0 1 1
//1 1 0 1 1 0 0
//1 0 0 0 1 0 0
//1 0 1 0 1 0 0
class Point {
    public int x,y;

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

public class Main {

    static int[] dx = {-1,-1,0,1,1,1,0,-1};
    static int[] dy = {0,1,1,1,0,-1,-1,-1};

    static int answer = 0;
    static int n =0;


    public static void main(String[] args) {

        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        int[][] arr = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = kb.nextInt();
            }
        }
        T.solution(arr);
        System.out.println(answer);

    }

    public void solution(int[][] board){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] == 1){
                    answer++;
                    board[i][j] = 0;
//                    DFS(i,j,board);
                    BFS(i,j,board);
                }
            }
        }
    }

    public void DFS(int x, int y, int[][] board) {
        for (int i = 0; i < 8; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny]==1){
                board[nx][ny] = 0;
                DFS(nx,ny,board);
            }
        }
    }

    Queue<Point> queue = new LinkedList<>();

    public void BFS(int x, int y, int[][] board) {
        queue.offer(new Point(x,y));
        while (!queue.isEmpty()){
            Point pos = queue.poll();
            for (int i = 0; i < 8; i++) {
                int nx = pos.x+dx[i];
                int ny = pos.y+dy[i];
                if(nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny]==1){
                    board[nx][ny] = 0;
                    queue.add(new Point(nx,ny));
                }
            }

        }
    }


}