[백준 1260] - [DFS BFS] DFS와 BFS (JAVA)

문제 링크 : https://www.acmicpc.net/problem/1260

---

이 문제는 DFS와 BFS를 제대로 이해하고 있는지 파악하는 문제로 보면 된다. 

이미 여러개의 DFS BFS 문제를 포스팅을  했지만 이번에 푼 문제가 이 문제여서 DFS와 BFS의 개념을 한번 복습을 해보자.

DFS는 깊이 우선 탐색(Depth First Search)의 약자이고 BFS는 너비 우선 탐색(Breadth First Search)의 약자이다.

노드들을 탐색할때 먼저 탐색된 노드의 자식노드를 우선적으로 탐색하는것을 말한다. 

만약 위의 노드들을 1을 기준으로 DFS로 조회한다고 하면 어떻게 될까?

먼저 기준점 1의 자식노드들을 확인한다. 

1의 자식노드들은 {2, 3} 이 있고 2부터 탐색을 시작한다.

2의 자식노드들은 4와 5가 있고 4를 먼저 탐색한다.

4는 자식노들 가지고 있지 않기에 4의 부모노드인 2가 남은 자식의 탐색을 시작한다.

2의 자식노드 4와 5중에 4는 탐색을 했고 남은 5를 탐색한다.

5를 탐색한뒤 5는 자식노드가 없고

5의 부모 노드인 2도 남은 자식노드가 없으니 2의 부모노드인 1로 돌아간다.

1은 아직 탐색하지 않은 자식 노드 3이 있고

위와 같은 방식으로 3 6을 탐색한다.

그럼 위의 트리에서의 DFS 순서는 [1, 2, 4, 5, 3, 6] 이 된다.

그럼 소스로 어떻게 구현을 할까?

이들은 재귀함수로 구현이 가능하다 

1) 탐색하려는 노드가 탐색을 이미 한 노드인지 확인하고

2) 탐색하려는 노드의 자식노드들을 확인한다.

3) 자식노드가 없으면 탐색은 종료되고

4) 자식노드가 있으면 자식노드를 같은 방식으로 탐색한다. 

아래 소스는 아주 기본적인 dfs 소스이다.

    public static void dfs(int node, boolean[] visited) {
        if(visited[node]) return;
        
        visited[node] = true;
 
        for(int nextNode:nodeList[node]) {
            dfs(nextNode, visited, sb);
        }
    }

DFS를 확인 했으면 이제 BFS를 확인한다.

BFS는 너비 우선 탐색이라고 했다

즉 형제 노드들을 우선으로 탐색한다는 뜻이다.

어렵게 생각하지말고 같은 레벨을 먼저 탐색한다 생각하면 된다.

1의 ROOT 이기 때문에 생략하고

1의 자식노드들은 2와 3인데 이 둘을 먼저 탐색하고 이 들의 자식노드들을 그 다음으로 탐색 또 그들의 자식노드들을 다음으로 탐색한다고 생각하면 된다.

모두들 같은 레벨에 위치해 있다. 

그럼 그림으로 보면서 DFS 와 어떻게 차이가 나는지 보자.

탐색의 시작은 1로 시작하고 1의 자식노들을 확인한다.

1의 자식노드들은 [2, 3] 이렇게 구성되고 이들을 큐에 삽입한다. 

현재 큐에는 [2, 3]  이렇게 데이터가 들어가 있을거고 이들을 하나씩 POP 하면서 꺼낸다.

처음 POP하면 추출되는 노드는 2가 되고 2를 탐색한다.

2를 탐색하고 2의 자식노드를 확인한다 [4, 5]가 발견됐고 이들을 큐에 삽입한다.

그럼 큐의 상태는[3, 4, 5] 가 된다. 2는 POP으로 추출 됐기에 큐에 존재 하지 않는다.

이제 큐에서 다시 POP하여 다음 탐색할 노드를 추출한다.

추출된 노드는 3이 되고 3의 자식노드를 확인하고 6이 나왔다.

3의 자식노드 6을 큐에 삽입하면 큐의 상태는 [4, 5, 6] 이된다.

나머지들도 큐에서 하나씩 추출해 가면서 탐색을 진행하게 되면

BFS의 탐색 순서는 [1, 2, 3, 4, 5, 6] 이 나오게 된다.

아래 소스는 BFS의 기본 소스이다.

    public static void bfs(int node, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<Integer>();
        
        queue.offer(node);
        
        while(!queue.isEmpty()) {
            node = queue.poll();
            
            if(visited[node]) continue;
            
            visited[node] = true;
            
            for(int nextNode:nodeList[node]) {
                queue.add(nextNode);
            }
        }
    }

그럼 백준 1260문제는 위의 두 소스를 가지고 풀면 된다. 

DFS와 BFS의 기본은 무조건 알아두어야 하고 알고리즘 문제에서 참 많은 비중으로 나온다고 한다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static int nodeCnt;
    public static LinkedList<Integer>[] nodeList;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        nodeCnt = Integer.parseInt(st.nextToken());
        int lineCnt = Integer.parseInt(st.nextToken());
        int startNode = Integer.parseInt(st.nextToken());
        
        nodeList = new LinkedList[nodeCnt+1];
        
        for(int i=0; i <= nodeCnt; i++) {
            nodeList[i] = new LinkedList<Integer>();
        }
        
        for(int i=0; i < lineCnt; i++) {
            st = new StringTokenizer(br.readLine());
            
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());
            
            nodeList[node1].add(node2);
            nodeList[node2].add(node1);
            
            Collections.sort(nodeList[node1]);
            Collections.sort(nodeList[node2]);
        }
        
        StringBuilder dfsResult = new StringBuilder();
        StringBuilder bfsResult = new StringBuilder();
        
        boolean[] dfsVisited = new boolean[nodeCnt+1];
        boolean[] bfsVisited = new boolean[nodeCnt+1];
        
        dfs(startNode, dfsVisited, dfsResult);
        bfs(startNode, bfsVisited, bfsResult);
        
        System.out.println(dfsResult + "\n" + bfsResult);
    }
    
    public static void dfs(int node, boolean[] visited, StringBuilder sb) {
        if(visited[node]) return;
        
        visited[node] = true;
        sb.append(node + " ");
        for(int nextNode:nodeList[node]) {
            dfs(nextNode, visited, sb);
        }
    }
    
    public static void bfs(int node, boolean[] visited, StringBuilder sb) {
        Queue<Integer> queue = new LinkedList<Integer>();
        
        queue.offer(node);
        
        while(!queue.isEmpty()) {
            node = queue.poll();
            
            if(visited[node]) continue;
            
            visited[node] = true;
            sb.append(node + " ");
            
            for(int nextNode:nodeList[node]) {
                queue.add(nextNode);
            }
        }
    }
}