[백준] 1260 DFS와 BFS

[백준] 1260 DFS와 BFS - Java

glorypang 2025. 4. 24. 15:45

728x90

SMALL

📌 문제 정보

출처: 문제 링크
난이도: ⭐⭐
문제 유형: DFS / BFS
사용 언어: Java

🔍 문제 설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

💡 풀이 노트

이 문제에서는 인접 리스트(ArrayList[])를 사용
- 정점 수 N이 최대 1,000이므로 인접 리스트가 메모리, 속도 면에서 유리
입력 받은 간선을 통해 양방향 그래프를 구성
탐색 순서 보장을 위해 각 정점의 인접 리스트를 오름차순 정렬

DFS (Depth-First Search) – 깊이 우선 탐색

현재 노드에서 갈 수 있는 정점을 먼저 깊게 파고들며 탐색
재귀를 사용하며, 방문한 노드는 `visited[]` 배열로 체크
노드 방문 시 바로 출력(`sb.append(v)`)

예:
1 → 2 → 4 → 3
깊이 우선이기 때문에 한 방향으로 끝까지 간 다음, 다시 돌아와서 이어서 탐색

BFS (Breadth-First Search) – 너비 우선 탐색

현재 노드와 인접한 모든 정점을 먼저 방문한 후, 그 다음 깊이로 넘어감
Queue를 이용하여 탐색 순서 유지
방문 시점에 `visited[]` 체크 & 큐에 추가

예:
1 → 2 → 3 → 4
같은 레벨(인접 정점)들을 먼저 방문하고 점점 넓게 퍼져 나감

`StringBuilder`를 사용하여 탐색 순서를 저장

🚀 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    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());

        graph = new ArrayList[N + 1];
        visited = new boolean[N + 1];

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

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

            graph[u].add(v);
            graph[v].add(u);
        }
        for(int i = 1; i <= N; i++){
            Collections.sort(graph[i]);
        }
        dfs(V);
        sb.append("\n");
        Arrays.fill(visited, false);
        bfs(V);
        System.out.println(sb);

    }

    public static void dfs(int v){
        visited[v] = true;
        sb.append(v).append(" ");
        for(int w : graph[v]){
            if(!visited[w]){
                dfs(w);
            }
        }
    }

    public static void bfs(int v){
        Queue<Integer> q = new LinkedList<>();
        visited[v] = true;
        sb.append(v).append(" ");
        q.add(v);

        while(!q.isEmpty()){
            int u = q.poll();
            for(int next : graph[u]){
                if(!visited[next]){
                    visited[next] = true;
                    sb.append(next).append(" ");

                    q.add(next);
                }
            }
        }
    }
}

🖥 실행 결과

입력

출력

1 2 4 3
1 2 3 4

📌 깃허브 코드 저장소: https://github.com/glorypang/CodingTest

728x90

LIST