JAVA BFS DFS 알고리즘

c++로만 구현했던 BFS와 DFS의 코드입니다.

자세한 설명은 아래 글을 참고해주세요.

https://wannadev.tistory.com/96

BFS, DFS c++

https://wannadev.tistory.com/116

BFS, DFS 활용 문제 고찰

 

 

코드 

 

 

 

dfs

import java.util.*;
import java.io.*;

public class Main {
    static int m;
    static int n;
    static int[][] graph;
    static class Node {
        int x;
        int y;
        public Node(int n, int m) {
            this.x = n;
            this.y = m;
        }
    }
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};

    static boolean dfs(int x, int y) {
        if (x<0 || x>=m || y<0 || y>=n) {
            return false;
        }
        if (graph[x][y] == 1) {
            graph[x][y] = 0;
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + x;
                int ny = dy[i] + y;
                dfs(nx,ny);
            }
            return true;
        }
        return false;
    }
    public static void main(String[] args) throws FileNotFoundException {
        //System.setIn(new FileInputStream("./input.txt"));
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            m = sc.nextInt(); n = sc.nextInt(); int k = sc.nextInt();
            graph = new int[m][n];
            for (int j = 0; j < k; j++) {
                int x = sc.nextInt(); int y = sc.nextInt();
                graph[x][y] = 1;
            }
            int ans = 0;
            for (int j = 0; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    if (graph[j][l] == 1) {
                        dfs(j, l);
                        ans++;
                    }
                }
            }
            System.out.println(ans);
        }
    }
}

 

 

BFS

import java.util.*;
import java.io.*;

public class Main {
    static int m;
    static int n;
    static class Node {
        int x;
        int y;
        public Node(int n, int m) {
            this.x = n;
            this.y = m;
        }
    }
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};

    static int[][] bfs(int x, int y, int[][] g) {
        Deque<Node> q = new ArrayDeque<>();
        g[x][y] = 0;

        q.add(new Node(x,y));
        while (!q.isEmpty()) {
            Node node = q.pollFirst();
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + node.x;
                int ny = dy[i] + node.y;
                if (0<=nx && nx<m && 0<=ny&& ny<n) {
                    if (g[nx][ny] == 1) {
                        g[nx][ny] = 0;
                        q.addLast(new Node(nx,ny));
                    }
                }
            }
        }
        return g;
    }
    public static void main(String[] args) throws FileNotFoundException {
        //System.setIn(new FileInputStream("./input.txt"));
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            m = sc.nextInt(); n = sc.nextInt(); int k = sc.nextInt();
            int[][] graph = new int[m][n];
            for (int j = 0; j < k; j++) {
                int x = sc.nextInt(); int y = sc.nextInt();
                graph[x][y] = 1;
            }
            int ans = 0;
            for (int j = 0; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    if (graph[j][l] == 1) {
                        graph = bfs(j, l, graph);
                        ans++;
                    }
                }
            }
            System.out.println(ans);
        }
    }
}