[백준] 1260번 DFS와 BFS

1) 생각

양방향 그래프에서 DFS(깊이 우선 탐색)과 BFS(넓이 우선 탐색)을 진행하여라.

처음 생각

DFS를 Stack으로 구현을 해보았고 재귀를 통해서도 구현을 하였다.

다음 생각

BFS를 Queue를 사용하여 구현을 하였다.

다다음 생각

DFS를 수행한 후 방문 배열 초기화를 해주지 않아 BFS값이 제대로 출력이 안됐었다.

2) 방안

1) DFS를 수행한 다음 BFS를 수행하기전 방문배열 초기화를 해주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int n,m,v;
    static List<ArrayList<Integer>> list;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        list = new ArrayList<>();
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());
        // list 초기화 점의 번호가 1부터 시작해서 0~n까지 생성
        for(int i=0;i<=n;i++)
            list.add(new ArrayList<>());
        
        for(int i=0;i<m;i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(a).add(b);
            list.get(b).add(a);
        }
        // 방문 할 수 있는 점이 여러개일경우 작은 번호부터 방문하라고 되어 있으므로
        // 각 점과 연결되어있는 점의 번호를 정렬해주자.
        for(int i=1;i<=n;i++)
            Collections.sort(list.get(i));
        
        visited = new boolean[n+1];
        dfs(v,0);
        sb.substring(0,sb.length()-1);
        sb.append("\n");
        Arrays.fill(visited, false);
        bfs();
        System.out.println(sb);
    }
    
    static boolean[] visited;
    private static void dfs(int vertex,int cnt) {
        sb.append(vertex+" ");
        visited[vertex] = true;
        for(int i=0;i<list.get(vertex).size();i++) {
            int t = list.get(vertex).get(i);
            if(visited[t]) continue;
            dfs(t,cnt+1);
        }
    }
    
    private static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v] = true;
        while(!queue.isEmpty()) {
            int t = queue.poll();
            sb.append(t+" ");
            for(int i=0;i<list.get(t).size();i++) {
                int tt = list.get(t).get(i);
                if(visited[tt]) continue;
                visited[tt] = true;
                queue.add(tt);
            }
        }
    }
}