백준 1260 - DFS와 BFS

문제 파악

BFS와 DFS를 한 순서대로 노드를 출력하는 문제

• DFS : 깊이 우선 탐색
  시작 정점으로부터 각 분기를 따라 가능한 멀리 탐색하는 기법
  깊이를 따라가다 더 이상 방문하지 않은 노드가 없으면 이전 정점으로 백트래킹하며 방문하지 않은 노드 탐색
  모든 노드를 다 방문해야할 때 유리
  -> 이 과정을 반복하기 때문에 반복문이나 재귀로 많이 풀게 됨
  위에서 시작 노드가 1이라고 했을 때, DFS를 실행하면 1 - 2 - 4 - 3
• BFS : 너비 우선 탐색
  시작 노드에서 가까운 노드부터 차례대로 탐색, 큐를 사용해 구현
  최단 경로 탐색에 유리
  따라서 가장 먼저 도착한 경로가 곧 최단 경로
  -> 위에서 시작 노드가 1이라고 했을 때, BFS를 실행하면
  1 - 2 - 3 - 4

풀이

1. 버퍼리더와 스트링 토크나이저를 사용해 첫째 줄에 정점의 개수 N, 간선의 개수 M, 시작할 정점의 번호 V를 입력받는다.
2. 둘째 줄에는 연결된 두 정점의 번호를 입력받아 ArrayList에 넣어놓는다.
   a. list[1] = [2, 3]이면 1번 노드는 2번과 3번에 연결된 것
3. 정점 번호가 작은 것부터 방문하도록 정렬한다.
4. DFS를 수행해 출력 값을 스트링 빌더에 넣어놓는다.
   a. 방문 처리 수행 (boolean형 배열로)
   b. 방문이 true인 것 하나씩 스트링 빌더에 넣어놓기
   c. 다음 노드 탐색 (방문 처리되지 않은 것 재귀 수행)
5. BFS를 수행해 출력 값을 스트링 빌더에 넣어놓는다.
   a. 방문 처리 수행 (boolean형 배열로)
   b. 큐에 넣기
   c. 큐에 있는 것을 꺼내면서 스트링 빌더에 넣어놓기
   d. 다음 노드 탐색 (방문 처리되지 않은 것 큐에 넣기)

코드

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

public class DFS와_BFS {
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();
    static ArrayList<Integer>[] graph;

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

        //정점의 개수 N 입력
        int N = Integer.parseInt(st.nextToken());
        //간선의 개수 M 입력
        int M = Integer.parseInt(st.nextToken());
        //시작 노드 번호 V 입력
        int V = Integer.parseInt(st.nextToken());

        //배열 생성
        //공간 만들어두기기
        graph = new ArrayList[N+1];
        //노드 1부터 N까지 각 배열 요소에 할당
        for (int i=1; i<=N; i++) {
            graph[i] = new ArrayList<>();
        }

        //간선 정보 입력
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a].add(b);
            graph[b].add(a);
        }

        //정점 번호가 작은 순서부터 방문하도록 정렬
        for (int i=1; i<=N; i++) {
            Collections.sort(graph[i]);
        }

        //방문 처리할 리스트 초기화
        visited = new boolean[N+1];
        //dfs 수행
        dfs(V);
        //한 줄 띄기기
        sb.append("\n");

        //방문 처리할 리스트 초기화
        visited = new boolean[N+1];
        //bfs 수행행
        bfs(V);
        
        System.out.println(sb);
    }

    public static void dfs(int v) {
        //현재 방문 노드 방문 처리
        visited[v] = true;
        //스트링빌더에 방문 노드 + 띄어쓰기 넣기
        sb.append(v).append(" ");
        //다음 노드에 대해해
        for (int next : graph[v]) {
            //방문 안 한 노드라면 dfs 수행행
            if (!visited[next]) {
                dfs(next);
            }
        }
    }

    public static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        //현재 방문 노드 방문 처리
        visited[v] = true;
        //현재 방문 노드 큐에 넣기
        queue.add(v);
        
        //큐가 빌때까지지
        while (!queue.isEmpty()) {
            //현재 노드 큐에서 꺼내서 스트링빌더에 넣기
            int current = queue.poll();
            sb.append(current).append(" ");
            
            //다음 노드에 대해
            for (int next : graph[current]) {
                if (!visited[next]) {
                    //방문 처리리
                    visited[next] = true;
                    //큐에 넣기기
                    queue.add(next);
                }
            }
        }
    }
}