[99클럽 코테 스터디 6일차 TIL / 백준] 1260 - DFS와 BFS (JAVA)

99클럽 코테스터디 6일차 TIL
KeyWord : BFS, DFS, graph

문제

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

입력

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

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

---

풀이

문제의 제목에서부터 알려주듯이, 깊이 우선 탐색 DFS와 너비 우선 탐색 BFS 기초 문제이다. 그래프가 무엇인지, DFS와 BFS가 무엇인지에 대해서만 알고 있다면 구현만 하면 된다.

DFS

재귀 호출로 쉽게 구현할 수 있다.

static void DFS(boolean[][] mat, int v) {  
    visited[v] = true;  
    dfs_sb.append(v).append(" ");  
    for (int i = 0; i < mat[v].length; i++) {  
        if(mat[v][i] && !visited[i])  
            DFS(mat, i);  
    }  
} 

여기서 주의할 점은 이미 방문했던 노드는 재방문하지 않는다는 것이다. 나는 visited 배열을 이용해 체크해주었다.

BFS

BFS는 큐를 이용하면 쉽게 구현할 수 있다. 노드와 연결된 모든 노드를 큐에 저장한 후 큐에 저장된 순서대로 방문하면 된다.

static void BFS(boolean[][] mat, int v) {  
    Queue<Integer> q = new LinkedList<>();  
    visited[v] = true;  
    q.add(v);  

    int len = mat[v].length;  

    while (!q.isEmpty()) {  
        int curNode = q.poll();  

        bfs_sb.append(curNode).append(" ");  
        for (int i = 0; i < len; i++) {  
            if (mat[curNode][i] && !visited[i]) {  
                visited[i] = true;  
                q.add(i);  
            }  
        }  
    }  
}

DFS와 마찬가지로, 주의할 점은 visited 배열을 통해 이미 방문했던 노드는 재방문하지 않아야 한다.

 

---

 

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.LinkedList;  
import java.util.Queue;  
import java.util.StringTokenizer;  

public class Main {  
    static boolean[] visited;  
    static StringBuilder dfs_sb = new StringBuilder();  
    static StringBuilder bfs_sb = new StringBuilder();  

    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  

        int n = Integer.parseInt(st.nextToken());  
        int m = Integer.parseInt(st.nextToken());  
        int v = Integer.parseInt(st.nextToken());  

        boolean[][] mat = new boolean[n+1][n+1];  

        for (int i = 0; i < m; i++) {  
            st = new StringTokenizer(br.readLine());  

            int p1 = Integer.parseInt(st.nextToken());  
            int p2 = Integer.parseInt(st.nextToken());  

            mat[p1][p2] = mat[p2][p1] = true;  
        }  

        visited = new boolean[n+1];  
        DFS(mat, v);  
        System.out.println(dfs_sb);  

        visited = new boolean[n+1];  
        BFS(mat,v);  
        System.out.println(bfs_sb);  
    }  

    static void DFS(boolean[][] mat, int v) {  
        visited[v] = true;  
        dfs_sb.append(v).append(" ");  
        for (int i = 0; i < mat[v].length; i++) {  
            if(mat[v][i] && !visited[i])  
                DFS(mat, i);  
        }  
    }  

    static void BFS(boolean[][] mat, int v) {  
        Queue<Integer> q = new LinkedList<>();  
        visited[v] = true;  
        q.add(v);  

        int len = mat[v].length;  

        while (!q.isEmpty()) {  
            int curNode = q.poll();  

            bfs_sb.append(curNode).append(" ");  
            for (int i = 0; i < len; i++) {  
                if (mat[curNode][i] && !visited[i]) {  
                    visited[i] = true;  
                    q.add(i);  
                }  
            }  
        }  
    }
}