BOJ) 1260 - DFS와 BFS

DFS 는 계속 했던 부분이었는데도 문제 이해를 잘 못한거지 출력에 약간 어려움이 있었고, BFS 는 이제 입문단계라 천천히 계속 풀어나가서 감을 잡아봐야겠다. 지금 느낌으로는 DFS 보다 BFS 가 쉬워 보인다는 느낌이 강하게든다. 익숙한 자료구조 Queue를 사용해서 그런거 같기도

풀이

노드 경로를 그대로 출력하는 느낌이라 따로 어려운 건 없어 보이고,
일반 dfs 같은 경우에는 시작에 depth 에 따른 종료 조건이 있어야하는데 이 문제는 그것과 다르게 시작 노드를 방문하고 부터 시작해야 한다는 점만 조심하면 될 것 같다.

package study;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class B_1260 {
    static int N, M, V;
    static boolean [] visited;
    static boolean [][] arr;
    static StringBuilder sb = new StringBuilder();
    static Queue<Integer> q = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        arr = new boolean[N+1][N+1];
        visited = new boolean[N+1];
        int a, b;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            arr[a][b] = arr[b][a] = true;
        }
        dfs(V);
        sb.append("\n");
        visited = new boolean[N+1];
        bfs(V);
        System.out.println(sb);
    }
    public static void dfs(int start){
        visited[start] = true;
        sb.append(start).append(" ");
        for (int i = 1; i < N+1; i++) {
            if (!visited[i] && arr[start][i]){
                dfs(i);
            }
        }
    }
    public static void bfs(int start){
        q.add(start);
        visited[start] = true;
        while (!q.isEmpty()){
            start = q.poll();
            sb.append(start).append(" ");

            for (int i = 1; i < N+1; i++) {
                if (arr[start][i] && !visited[i]){
                    q.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}