[JAVA] 백준 "DFS와 BFS"

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

 

가장 DFS와 BFS의 기본적인 유형이다.

 

살펴봐야할 포인트를 하나씩 짚어보겠다.

먼저 전체코드를 서두에 올려놓겠다.

 

전체코드

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

public class Main {
    //함수에서 사용할 변수들
    static int[][] check; //간선 연결상태
    static boolean[] checked; //확인 여부
    static int n; //정점개수
    static int m; //간선개수
    static int start; //시작정점

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        start = sc.nextInt();

        check = new int[1001][1001]; //좌표를 그대로 받아들이기 위해 +1해서 선언
        checked = new boolean[1001]; //초기값 False

        //간선 연결상태 저장
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            check[x][y] = check[y][x] = 1;
        }

        dfs(start); //dfs호출

        checked = new boolean[1001]; //확인상태 초기화
        System.out.println(); //줄바꿈

        bfs(); //bfs호출
    }

    //시작점을 변수로 받아 확인, 출력 후 다음 연결점을 찾아 시작점을 변경하여 재호출
    public static void dfs(int i) {
        checked[i] = true;
        System.out.print(i + " ");

        for (int j = 1; j <= n; j++) {
            if (check[i][j] == 1 && checked[j] == false) {
                dfs(j);
            }
        }
    }

    public static void bfs() {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(start); //시작점도 Queue에 넣어야 함
        checked[start] = true;
        System.out.print(start + " ");

        //Queue가 빌 때까지 반복. 방문 정점은 확인, 출력 후 Queue에 넣어 순서대로 확인
        while (!queue.isEmpty()) {
            int temp = queue.poll();

            for (int j = 1; j <= n; j++) {
                if (check[temp][j] == 1 && checked[j] == false) {
                    queue.offer(j);
                    checked[j] = true;
                    System.out.print(j + " ");
                }
            }
        }
    }
}

 

1. check / checked 배열

check = new int[1001][1001]; //좌표를 그대로 받아들이기 위해 +1해서 선언
checked = new boolean[1001]; //초기값 False

//간선 연결상태 저장
for (int i = 0; i < m; i++) {
     int x = sc.nextInt();
     int y = sc.nextInt();

     check[x][y] = check[y][x] = 1;
}

양방향 간선이기때문에 check[x][y] 와 check[y][x]는 같다.

 

이때, 좌표를 그대로 받아들이기 위해 +1해서 선언한다.

 

2. public static void dfs(int i)

 public static void dfs(int i) {
        checked[i] = true;
        //System.out.print(i + " ");

        for (int j = 1; j <= n; j++) {
            if (check[i][j] == 1 && checked[j] == false) {
                dfs(j);//연결o, 방문x 이면 점점 깊숙히 호출
            }
        }
}

- 연결이 되어있는지 확인

- 방문하지 않은 노드인지 확인

 

3. public static void bfs()

public static void bfs() {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(start); //시작점도 Queue에 넣어야 함
        checked[start] = true;
        //System.out.print(start + " ");

        //Queue가 빌 때까지 반복. 방문 정점은 확인, 출력 후 Queue에 넣어 순서대로 확인
        while (!queue.isEmpty()) {
            int temp = queue.poll();

            for (int j = 1; j <= n; j++) {
                if (check[temp][j] == 1 && checked[j] == false) {
                    queue.offer(j);
                    checked[j] = true;
                    //System.out.print(j + " ");
                }
            }
        }
}

- Queue 구현 LinkedList 기반

- checked[start] = true 로 시작지점 방문 체크.

- 큐가 빌때까지 계속 큐에서 빼내서 작업

- 빼낸 노드에서 갈수있는 모든 노드들(연결o, 방문x)을 큐에 차례대로 넣고, 방문처리.