백준 알고리즘 1260번: DFS와 BFS

문제 정보

---

1260번: DFS와 BFS

 

 

핵심

---

DFS와 BFS에 대해서 알고 있는지?

그래프를 탐색하는 알고리즘에 대한 지식을 가지고 있는지?

그들을 어떤 Data Structure를 통해 구현해야 하는지 알고 있는지?

 

개인적으로 내부 알고리즘에서 중요한 요소는 이렇게 된다고 생각한다

- 해당 노드를 방문했는지 확인하는 boolean visitied[]

- 노드들 사이 간선을 판단하는 boolean edge[][]

- BFS의 경우 FIFO를 가능케 하는 Queue<>

 

DFS는 대부분 Stack을 통하여 구현한다

1. 시작 노드를 Stack에 삽입한다

2. Stack에서 한 요소를 pop하고 출력한다. 이 때, 해당 노드를 방문한 것으로 표시한다

3. pop한 노드와 간선으로 연결된 다른 노드들 중, 방문하지 않은 노드를 Stack에 삽입한다

4. 2~3의 과정을 반복하고, 모든 노드가 방문되었다면 프로그램을 종료한다

 

BFS는 대부분 Queue를 통하여 구현한다

1. 시작 노드를 Queue에 삽입한다

2. Queue에서 한 요소를 pop하고 출력한다. 이 때, 해당 노드를 방문한 것으로 표시한다

3. pop한 노드와 간선으로 연결된 다른 노드들 중, 방문하지 않은 노드를 Queue에 삽입한다

4. 2~3의 과정을 반복하고, 모든 노드가 방문되었다면 프로그램을 종료한다

 

 

풀이

---

// 1260: DFS, BFS
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[][] edge;
    static boolean[] visited;
    static StringBuilder sb;
    static Queue<Integer> queue;

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

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

        edge = new boolean[N][N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            edge[n1][n2] = true;
            edge[n2][n1] = true;
        }
        visited = new boolean[N];
        sb = new StringBuilder();
        dfs(V, N, 0);
        System.out.println(sb.toString());
        visited = new boolean[N];
        sb = new StringBuilder();
        queue = new LinkedList<>();
        bfs(V, N, 0);
        System.out.println(sb.toString());
    }

    public static void dfs(int current, int end, int depth) {
        if (depth == end)
            return;
        visited[current] = true;
        sb.append(current + " ");
        for (int i = 1; i < end; i++) {
            if (edge[current][i] && !visited[i]) {
                dfs(i, end, depth + 1);
            }
        }
    }

    public static void bfs(int current, int end, int depth) {
        if (depth == end)
            return;
        visited[current] = true;
        sb.append(current + " ");
        for (int i = 1; i < end; i++) {
            if (edge[current][i] && !visited[i]) {
                visited[i] = true;
                queue.add(i);
            }
        }
        if (!queue.isEmpty())
            bfs(queue.remove(), end, depth + 1);
    }
}

나는 DFS의 경우 인접 행렬 방식으로 풀이했는데,

그 이유는 문제에서

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 

해당 조건이 주어져있었기 때문에, 일부러 정렬을 해줄 필요가 없이 for loop 을 통하여 인접한 행렬을

Recursive call을 통하여 번호가 작은 노드부터 차례대로 방문할 수 있게 해 주었다

 

고찰

---

중간중간에 depth와 같은 variable은 사용하지 않아도 풀 수 있을 것 같아 불필요해 보였다

또한, main->dfs나 main->bfs로 여러 variable을 넘겨주기 위하여 global variable 처리를 하고 풀이하였는데

이부분을 더 효율적으로 구현할 수 있는 방법이 있을것 같다

 

아래 코드는 백준 알고리즘 다른사람 풀이를 참고하면서, 내가 구현하고 싶었던 대로 깔끔하게 구현되어 있는 코드를 찾아 가져와 보았다

// 출처 : https://www.acmicpc.net/source/54591054
import java.util.*;
import java.io.*;

class Main {
    static int N, M, R;
    static boolean[] visited;
    static ArrayList<Integer>[] graph;
    static ArrayList<Integer> dfsAns = new ArrayList<>();
    static ArrayList<Integer> bfsAns = new ArrayList<>();
    static Queue<Integer> queue = new LinkedList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        visited = new boolean[N+1];
        graph = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph[u].add(v);
            graph[v].add(u);
        }
        for (int i = 1; i <= N; i++) Collections.sort(graph[i]);
        dfs(R);
        bfs(R);

        StringBuilder sb = new StringBuilder();
        for (int i : dfsAns) sb.append(i).append(" ");
        sb.append("\n");
        for (int i : bfsAns) sb.append(i).append(" ");
        System.out.println(sb);
    }
    static void dfs(int r) {
        visited[r] = true;
        dfsAns.add(r);
        for (int adj : graph[r]) {
            if (!visited[adj]) {
                dfs(adj);
            }
        }
    }
    static void bfs(int r) {
        visited = new boolean[N+1];
        visited[r] = true;
        bfsAns.add(r);
        queue.add(r);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int adj : graph[u]) {
                if (!visited[adj]) {
                    visited[adj] = true;
                    bfsAns.add(adj);
                    queue.add(adj);
                }
            }
        }

    }
}

인접 행렬을 2중 Array를 사용하지 않고, 2중 List를 사용하여 풀이하셨고

이러한 경우 장점은 foreach로 해당 노드와 인접한 노드를 탐방할 수 있어서 연결되어 있는지 굳이 확인할 필요 없어서 더 효율적인 것 같다

하지만 이 경우에 아까 말했던 특정 노드와 연결된 노드가 한 개 이상인 경우, 가장 작은 노드부터 방문해야 하기 때문에

Collections.sort() 를 사용하여 정렬을 꼭 해주어야 하는 단점이 있다!

 

Source Code

---