[백준] 1260번 : DFS와 BFS

1260번: DFS와 BFS

---

문제

---

예제

---

 

풀이

그래프 탐색 알고리즘인 DFS(깊이 우선 탐색)과 BFS(넓이 우선 탐색)을 활용한 대표적인 문제이다.

 

DFS (깊이 우선 탐색)

출처 : 위키백과

DFS는 쉽게 말하면 한 우울만 파는 것이다.

이렇게 DFS는 재귀와 스택(stack)을 통해서 구성이 가능하다.

문제의 첫번째 예제를 확인해보면 다음과 같다.

4개의 정점 ( 1, 2, 3, 4 )이 있고 5개의 간선이 있으며 정점 1부터 확인을 시작한다는 의미이다.

그리고 예제와 같이 간선이 연결되어 있다고 가정을 하면,

정점 1과 연결되어 있는 정점은 2, 3, 4이다.

그럼 1과 가장 가까운 2를 또 깊이 탐색에 들어간다.

정점 2와 연결되어 있는 정점은 1, 4 이다.

정점 1은 이미 확인했으므로 4를 깊이 탐색한다.

4와 연결된 정점은 1, 2, 3이다.

정점 1과 2는 이미 확인 했음으로 끝이 난다.

이렇게 확인한 순서는 1, 2, 4, 3이 된다.

 

BFS (넓이 우선 탐색)

출처 : 위키백과

BFS는 한 깊이씩 차례로 확인하며 내려가는 방법이다.

BFS는 Queue와 LinkedList를 통해서 구성이 가능하다.

이번에도 문제의 첫번째 예제를 통해 확인해 보자.

1번과 연결된 정점은 2, 3, 4번이다.

그럼 2, 3, 4의 값을 Queue에 넣어서 방문 기록을 남김과 동시에 방문한 값을 출력한다.

큐에 담긴 값들을 순차적으로 poll() 하면서 큐 자료를 삭제하면서 다음 값으로 이동한다.

이렇게 동일 깊이의 값들을 순회하면서 마지막 값까지 다다르게 된다.

그렇게 1, 2, 3, 4의 순서대로 정점을 확인하게 된다.

---

소스 코드

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

public class Main {

    // 함수에서 사용하는 변수
    static int[][] check; // 간선 연결상태
    static boolean[] visit; // 확인 여부
    static int N; // 정점 개수
    static int M; // 간선 개수
    static int V; // 시작 정점

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

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

        // 간선 연결상태 저장
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

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

        DFS(V); // DFS 호출

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

        BFS(); // BFS 호출
    }

    public static void DFS(int i) {
        visit[i] = true;
        System.out.print(i + " ");

        for (int j = 1; j <= N; j++) {
            if (check[i][j] == 1 && visit[j] == false) {
                DFS(j);
            }
        }
    }

    public static void BFS() {
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(V); // 시작점도 Queue에 저장
        visit[V] = true;
        System.out.print(V + " ");

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

            for (int j = 1; j <= N; j++) {
                if (check[tmp][j] == 1 && visit[j] == false) {
                    q.offer(j);
                    visit[j] = true;
                    System.out.print(j + " ");
                }
            }
        }
    }
}

 

---

참고

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전