백준 DFS와BFS java

문제링크

문제 접근

• 백준 예전에 풀었던 문제들 다시 풀어보는 중
• 입력 노드들 리스트 배열에 담아서 dfs , bfs 순서로 돌리면 됨

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class baek_1260 {
    static ArrayList<Integer> list [];
    static boolean[] visit;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());
        visit = new boolean[N+1];
        list = new ArrayList[N+1];
        for(int i=1;i<=N;i++){
            list[i] = new ArrayList<>();
        }
        for(int m=0;m<M;m++){
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            list[S].add(E);
            list[E].add(S); // 양방향 간선
        }
        for(int i=1;i<=N;i++){
            Collections.sort(list[i]); //작은 노드부터 탐색하라고 했으므로 정렬
        }
        dfs(N,V);
        System.out.println(sb.toString());
        bfs(N,V);
    }
    private static void dfs(int N,int V){
        visit[V] = true;
        sb.append(V+" ");
        for(int i=0;i < list[V].size();i++){
            int now = list[V].get(i);
            if(!visit[now]) dfs(N,now);
        }

    }
    private static void bfs(int N,int V){
        StringBuilder sb = new StringBuilder();
        boolean[] visit = new boolean[N+1];
        Queue<Integer> que = new LinkedList<>();
        que.add(V);
        visit[V] = true;
        sb.append(V);
        while(!que.isEmpty()){
            int now = que.poll();
            for(int i=0;i<list[now].size();i++){
                int next = list[now].get(i);
                if(visit[next]) continue;
                que.add(next);
                visit[next] = true;
                sb.append(" "+next);
            }
        }
        System.out.println(sb.toString());
    }
}

정리

• bfs는 오랜만에 해도 안 헤매는데 dfs는 재귀접근에 살짝 고민하게 됨
• 꾸준히 다시 풀자