Algorithm

그래프 / 백준 1260 DFS와 BFS

Dear-J 2025. 6. 8. 20:30

 

문제 접근

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);
                }
            }
        }
    }
}

'Algorithm' 카테고리의 다른 글

그래프 / 백준 1707 이분 그래프  (0) 2025.06.09
그래프 / 백준 11724 연결 요소의 개수  (0) 2025.06.08
그래프 / 백준 13023 ABCDE  (0) 2025.06.05
BF / 백준 6603 로또  (0) 2025.06.05
BF / 백준 10971 외판원 순회 2  (0) 2025.06.05