그래프 / 백준 1260 DFS와 BFS

 

문제 접근

DFS

1. 이미 방문한 노드라면 그냥 return 
2. 아니면 visit 배열을 true로 바꿔주고, StringBuilder에 추가
3. 해당 노드의 인접리스트를 돌면서 방문하지 않은 노드에 대하여 DFS()를 실행 (재귀)

BFS

1. 맨 처음에 시작노드를 큐에
2. while문은 큐가 empty 될때까지 반복

While문 내부

1. 꺼내면서 값을 저장
2. 꺼냈는데 visit 배열이 false면 StringBuilder에 추가, true로
3. now 노드의 인접리스트를 돌면서 방문하지 않은 노드가 있다면 큐에
4. 반복

풀이

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

public class S1260 {
    static int N, M, V;
    static boolean[] visit1, visit2;
    static ArrayList<Integer>[] edgeList;
    static Queue<Integer> queue = new LinkedList<>();
    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());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        visit1 = new boolean[N + 1];
        visit2 = new boolean[N + 1];
        edgeList = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            edgeList[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            edgeList[from].add(to);
            edgeList[to].add(from);
        }

        for (int i = 1; i <= N; i++) {
            edgeList[i].sort(Comparator.naturalOrder());
        }

        dfs(V);
        sb.append("\n");

        bfs(V);

        System.out.println(sb);
    }

    static void dfs(int start) {
        if (visit1[start]) {
            return;
        }

        visit1[start] = true;
        sb.append(start).append(" ");
        for (int to : edgeList[start]) {
            if (!visit1[to]) {
                dfs(to);
            }
        }
    }

    static void bfs(int start) {
        queue.offer(start);

        while (!queue.isEmpty()) {
            int now = queue.poll();

            if (!visit2[now]) {
                sb.append(now).append(" ");
            }
            visit2[now] = true;

            for (int to : edgeList[now]) {
                if (!visit2[to]) {
                    queue.offer(to);
                }
            }
        }
    }
}