[백준] 1260번: DFS와 BFS (Java)

문제: https://www.acmicpc.net/problem/1260

📌 문제 탐색하기

입력 : 첫째 줄 - 정점의 개수 N (1 ≤ N ≤ 1,000) / 간선의 개수 M (1 ≤ M ≤ 1,000) / 탐색을 시작할 정점의 번호 V
M개의 줄 - 간선이 연결하는 두 정점의 번호
두번째 줄의 수만큼 세번째 줄 반복
출력 : V부터 방문된 점을 순서대로 출력한다.

가능한 시간복잡도

O(V + E)
V : 정점의 수
E : 간선의 수

알고리즘 선택

DFS, BFS

📌 코드 설계하기

1. BufferedReader를 사용하여 입력을 받는다.
2. 각 정점의 인접 리스트를 저장하기 위해 ArrayList의 배열을 사용한다. 그래프는 무방향 그래프이므로 각 간선은 양방향으로 저장된다.
3. 각 정점에 연결된 다른 정점들을 번호가 작은 순서대로 방문하기 위해 인접 리스트를 사전에 정렬한다.
4. 재귀를 사용해 DFS를 구현하며, 방문한 정점을 visited 배열을 통해 체크한다.
5. Queue를 사용하여 BFS를 구현하며, 방문한 정점 역시 visited 배열로 관리한다.
6. V부터 방문된 점을 순서대로 출력하낟.

📌 시도 회차 수정 사항 (Optional)

💡 시도별 수정 사항은 어떻게 작성하나요?
- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

1회차

2회차

📌 정답 코드

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

public class Main {
    private static ArrayList<Integer>[] adjacencyList;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);
        int v = Integer.parseInt(inputs[2]); 

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

        for (int i = 0; i < m; i++) {
            inputs = br.readLine().split(" ");
            int u = Integer.parseInt(inputs[0]);
            int w = Integer.parseInt(inputs[1]);
            adjacencyList[u].add(w);
            adjacencyList[w].add(u);
        }

        for (int i = 1; i <= n; i++) {
            Collections.sort(adjacencyList[i]);
        }

        visited = new boolean[n + 1];
        dfs(v);
        sb.append("\n");

        visited = new boolean[n + 1];
        bfs(v);

        System.out.print(sb.toString());
    }

    private static void dfs(int node) {
        visited[node] = true;
        sb.append(node).append(" ");
        for (int neighbor : adjacencyList[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    }

    private static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            sb.append(node).append(" ");
            for (int neighbor : adjacencyList[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }
}