[백준] 1260 DFS와 BFS

문제 링크:

1260번: DFS와 BFS

 

문제:

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

입력:

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

출력:

 

문제 이해 및 해결 방향:

첫줄에는 N , M ,V 가 주어진다. N은 정점 개수, M은 간선 개수, V는 시작 vertex이다.

그 다음 부터는 두 정점에 연결된 간선을 M개만큼 작성한다. 예를들면 1 2인 경우 1과 2사이에 간선이 존재한다는 것이다.

 

먼저 DFS를 해결하기 위해서 예제 입력 2로 설명한다. 

위 그림이 DFS방식이다. 즉 위 그림을 코드로 구현하기 위해서 재귀 방식을 사용한다.

시작을 기점으로 인접한 노드를 확인하며 방문을 하지 않았다면 이동해 이를 전부 방문할때까지 반복하면 되는 것이다.

이를 그대로 코드로 구현하면 다음과 같다.

    public static void dfs(int V, boolean[][] nodes, boolean[] visited){
        /**
         * node[i][j] = i j가 true면 i와 j가 연결된 간선이 존재한다는 변수
         */
        visited[V] = true; // 방문 표시
        System.out.print(V + " ");

        for(int i = 1; i < nodes[V].length; i++){
            // 방문하지 않았고 간선이 존재하는 경우
            if(!visited[i] && nodes[V][i]){
                dfs(i, nodes, visited);
            }
        }
    }

 

 

다음은 BFS 방식이다. 이를 해결하기 위해서 다음과 같은 그림으로 설명한다.

BFS는 queue방식이 가장 이해하기 쉽고 자주 사용한다.

즉 시작점을 queue에 넣은 상태로 시작하며,

pop하여 이를 출력하고 그 인접한 노드들을 위 그림과 같이 queue에 넣어주면 된다.

 

이를 코드로 그대로 구현하면 다음과 같다.

    public static void bfs(int V, boolean[][] nodes, boolean[] visited){
        Queue<Integer> q = new LinkedList<>();
        visited[V] = true; // 방문 표시
        q.add(V);

        // 큐가 비어있을 때까지 큐를 pop 하면서 인접한 곳 모두 방문
        while(!q.isEmpty()){
            int v = q.poll();
            System.out.print(v + " ");
            for(int i = 1; i < nodes[v].length; i++){
                // 방문하지 않았고 간선이 존재하는 경우
                if(!visited[i] && nodes[v][i]){
                    visited[i] = true;
                    q.add(i);
                }
            }
        }
    }

 

 

최종 코드:

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

public class Main {

    public static void dfs(int V, boolean[][] nodes, boolean[] visited){
        /**
         * node[i][j] = i j가 트루이면 i와 j가 연결된 간선이 존재한다는 변수
         */
        visited[V] = true; // 방문 표시
        System.out.print(V + " ");

        for(int i = 1; i < nodes[V].length; i++){
            // 방문하지 않았고 간선이 존재하는 경우
            if(!visited[i] && nodes[V][i]){
                dfs(i, nodes, visited);
            }
        }
    }

    public static void bfs(int V, boolean[][] nodes, boolean[] visited){
        Queue<Integer> q = new LinkedList<>();
        visited[V] = true; // 방문 표시
        q.add(V);

        // 큐가 비어있을 때까지 큐를 pop 하면서 인접한 곳 모두 방문
        while(!q.isEmpty()){
            int v = q.poll();
            System.out.print(v + " ");
            for(int i = 1; i < nodes[v].length; i++){
                // 방문하지 않았고 간선이 존재하는 경우
                if(!visited[i] && nodes[v][i]){
                    visited[i] = true;
                    q.add(i);
                }
            }
        }
    }

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

        int N, M, V;
        int v1, v2; // v1과 v2와 연결된 간선

        // N, M, V 입력
        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());

        // 방문 여부
        boolean[] visited = new boolean[N + 1];
        boolean[][] nodes = new boolean[N + 1][N + 1];

        // 간선 정보 입력
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());
            nodes[v1][v2] = true; // 간선이 있다는 것을 true
            nodes[v2][v1] = true;
        }

        dfs(V, nodes, visited); // dfs 탐색 실행
        System.out.println();

        // dfs에서 사용했기 때문에 방문 초기화
        for (int i = 0; i <= N; i++) {
            visited[i] = false;
        }

        bfs(V, nodes, visited); // bfs 탐색 실행
    }
}

 

 

결론:

DFS, BFS 알고리즘을 익히는 입문자 분들에게 추천하는 문제이다.

작성자는 DFS는 재귀로, BFS는 Queue로 푸는것을 추천한다.

 

감사합니다.