[알고리즘] 백준_DFS와 BFS - 1260

너비 우선 탐색(BFS)

• 그래프를 완전 탐색하는 방법

• 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

• 선입선출 방식으로 큐를 이용해 구현

• 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로 보장

• 시간 복잡도 : O(V(노드 수)+E(에지 수))

너비 우선 탐색 핵심 이론

• BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화
  • 방문했던 노드는 다시 방문 X -> 방문 노드 체크 배열
  • 그래프 인접 리스트로 표현 -> DFS와 동일
  • 큐로 표현
• 큐에서 노드를 꺼낸 후 꺼낸방문 노드의 인접 노드를 큐에 삽입
  • 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입 X
  • 탐색 순서에 기록
• 큐 자료구조에 값이 없을 때까지 반복

문제 설명

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

입력

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

출력

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

문제 분석 및 해결 방법

DFS와 BFS를 각각 구현해야 하므로, 우선 인접 리스트에 그래프를 저장한 후, DFS를 실행하면서 방문 배열을 체크하고 탐색 노드를 DFSresult에 저장해준다.
BFS도 노드를 큐에 삽입해주고, poll하면서 탐색 노드를 BFSresult에 저장해주면 된다.

여기서 번호가 작은 것을 먼저 방문하기 위해서 인접 리스트를 먼저 정렬한 후 실행해준다.

추가로, DFS, BFS를 하기 전 방문 배열을 초기화해줘야 올바른 답이 나온다. 이후 저장된 result를 출력해주면 된다.

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

public class Main {
    static ArrayList <Integer> [] list;
    static boolean visited [];
    static ArrayList <Integer> DFSresult;
    static ArrayList <Integer> BFSresult;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());
        DFSresult = new ArrayList<>();
        BFSresult = new ArrayList<>();

        list = new ArrayList[N+1];
        
        // 인접 리스트 초기화
        for(int i=1;i<N+1;i++){
            list[i] = new ArrayList<>();
        }
        for(int i=1;i<M+1;i++){
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            list[num1].add(num2);
            list[num2].add(num1);
        }
        
        // 번호가 작은 것을 먼저 방문하기 위해 정렬
        for(int i=1;i<N+1;i++){
            Collections.sort(list[i]);
        }
        
        visited = new boolean[N+1];
        DFS(V);
        for(int i:DFSresult){
            bw.write(i+" ");
        }
        bw.newLine();
        
        visited = new boolean[N+1];
        BFS(V);
        for(int i:BFSresult){
            bw.write(i+" ");
        }
        bw.flush();
      }
    static void DFS(int num) {
        DFSresult.add(num);
        visited[num] = true;

        for(int i : list[num]) {
            if(visited[i]==false){
                DFS(i);
            }
        }
    }
    static void BFS(int num) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
        visited[num] = true;

        while(!queue.isEmpty()){
            int now_Node = queue.poll();
            BFSresult.add(now_Node);
            for(int i:list[now_Node]){
                if(!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

참고 : Do it! 알고리즘 코딩테스트 with JAVA