[자바문법] BFS || DFS || PriorityQueue 공식 정리

BFS 공식 (너비우선탐색)

1. 일반 BFS

private static int[] hor = {-1, 1, 0, 0};
private static int[] ver = {0, 0, -1, 1};
private static int N = 5;
private static int M = 5;
private static int[][] box; 

private static void BFS() {
    Deque<Node> dq = new ArrayDeque<>();
    dq.add(new Node(0,0, 0));

    while(!dq.isEmpty()) {
        Node now = dq.poll();
        for(int i = 0; i <4 ; i++) {
            int nowY = now.Y + hor[i];
            int nowX = now.X + ver[i];
            int today = now.day;                
            if(0<= nowY && nowY < N && 0<= nowX && nowX < M) {
                if(box[nowY][nowX]==0) {
                    box[nowY][nowX] = 1;
                    dq.add(new Node(nowX, nowY, today+1));
                }
            }
        }
    }
}

1-2. 상하좌우 덩어리 크기 및 총 덩어리 개수 파악 BFS

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

public class RecogObstacle {
    static int[] ver = {-1, 1, 0, 0};
    static int[] hor = {0, 0, -1, 1};
    static int[][] matrix;
    static boolean[][] visited;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        matrix = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String[] arr = br.readLine().split("");
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(arr[j]);
            }
        }

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 1 && !visited[i][j]) {
                    list.add(BFS(i, j));
                }
            }
        }
        bw.write("" + list.size() + "\n");
        list.sort(Comparator.naturalOrder());
        for (int i = 0; i < list.size(); i++) bw.write("" + list.get(i) + "\n");

        bw.close();
    }

    private static int BFS(int nowI, int nowJ) {
        Deque<Node> dq = new ArrayDeque<>();
        dq.add(new Node(nowI, nowJ));
        int count = 0;
        while (!dq.isEmpty()) {
            Node now = dq.poll();
            count++;
            visited[now.Y][now.X] = true;

            for (int dir = 0; dir < 4; dir++) {
                int nowY = now.Y + ver[dir];
                int nowX = now.X + hor[dir];

                if (0 <= nowY && nowY < N && 0 <= nowX && nowX < N) {
                    if (matrix[nowY][nowX] == 1 && !visited[nowY][nowX]) {
                        dq.add(new Node(nowY, nowX));
                        visited[nowY][nowX] = true;
                    }
                }
            }
        }
        return count;
    }

    private static class Node {
        private int Y;
        private int X;

        public Node(int Y, int X) {
            this.Y = Y;
            this.X = X;
        }
    }
}

 

---

DFS 공식 (깊이우선탐색)

2. 일반 DFS

static Integer node;
static Integer edge;
static int [][] matrix;
static boolean [] visited;
public static String solution(String title) throws IOException {
    String answer = title;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    node = Integer.parseInt(st.nextToken());
    edge = Integer.parseInt(st.nextToken());
    matrix = new int[node+1][node+1];
    visited = new boolean[node+1];
    // 행렬에 연결되는 노드에 1으로 체크(방향이 없으므로 양방향 1체크)
    for(int i=0; i<edge; i++) {
        StringTokenizer edgeSt = new StringTokenizer(br.readLine(), " ");
        int start = Integer.parseInt(edgeSt.nextToken());
        int end = Integer.parseInt(edgeSt.nextToken());
        matrix[start][end] = 1;
        matrix[end][start] = 1;
    }
    int count = 0;
    // 방문한 열을 돌면서, 안가본 정점이 있으면 탐색을 시작하고, 덩어리수 +1
    for(int i=1 ; i<=node ; i++) {
        if(!visited[i]) {
            DFS(i);
            count++;
        }
    }
    return answer;
}
private static void DFS (int start) {
    // 방문 체크
    visited[start] = true;
    // 방문한 행을 돌면서, 간선이 연결된 애들에 한해서, 안가본 곳이면 가봐라
    for(int i =1; i<=node ; i++) {
        if(matrix[start][i]==1 && !visited[i]) DFS(i);
    }
}

 

 

 

---

PriorityQueue 공식(우선순위 큐)

1. 기본 PriorityQueue

public static void main(String[] args) {
	PriorityQueue<Node> queue = new PriorityQueue<>((a,b)-> a.X - b.X); // 오름차순
    PriorityQueue<Node> queue = new PriorityQueue<>((a,b)-> b.X - a.X); // 내림차순
    ...
}

private static class Node {
	private int X;
    private int Y;
	public Node(int x, int y) {
    	this.X = x;
        this.Y = y;
    }
}