백준 1260번: 그래프 탐색 (DFS와 BFS)

문제 설명

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

백준 1260번 문제는 주어진 그래프에 대해 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 수행하는 문제입니다. 

입력으로 정점의 개수, 간선의 개수, 시작 정점을 받고, 그래프의 간선 정보를 이용해 탐색 결과를 출력합니다.

 

문제 해결 전략

그래프 표현:

• 그래프는 인접 리스트 방식으로 표현합니다.
• Map<Integer, List<Integer>>를 사용하여 각 정점에 대한 인접한 정점 리스트를 저장합니다.

탐색 알고리즘 구현:

• DFS는 재귀를 통해 구현하고, BFS는 큐를 사용하여 구현합니다.
• 두 알고리즘 모두 방문한 정점을 기록하여 중복 방문을 방지합니다.

입력 및 출력:

• 표준 입력을 통해 그래프 정보를 읽고, 탐색 결과를 표준 출력으로 작성합니다.

 

코드

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

class Main {
    private static int N; // 정점의 개수
    private static int M; // 간선의 개수
    private static int V; // 시작 정점
    private static final Map<Integer, List<Integer>> graph = new HashMap<>();

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            init(br);
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            getResult(bw);
        } catch (IOException e) {
            System.out.println("error: " + e.getMessage());
        }
    }

    private static void init(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        // 그래프 초기화
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int key = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            graph.putIfAbsent(key, new ArrayList<>());
            graph.putIfAbsent(value, new ArrayList<>());
            graph.get(key).add(value);
            graph.get(value).add(key); // 무방향 그래프
        }

        // 각 인접 리스트를 정렬
        for (List<Integer> neighbors : graph.values()) {
            Collections.sort(neighbors);
        }
    }

    private static void getResult(BufferedWriter bw) throws IOException {
        bw.write(dfs(V));
        bw.newLine();
        bw.write(bfs(V));
        bw.flush();
        bw.close();
    }

    private static String dfs(int start) {
        StringBuilder result = new StringBuilder();
        Set<Integer> visited = new HashSet<>();
        dfsHelper(start, visited, result);
        return result.toString().trim();
    }

    private static void dfsHelper(int node, Set<Integer> visited, StringBuilder result) {
        visited.add(node);
        result.append(node).append(" ");

        for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
            if (!visited.contains(neighbor)) {
                dfsHelper(neighbor, visited, result);
            }
        }
    }

    private static String bfs(int start) {
        StringBuilder result = new StringBuilder();
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        visited.add(start);
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.append(node).append(" ");
            
            for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        return result.toString().trim();
    }
}

코드 설명
정점의 개수, 간선의 개수, 시작 정점을 입력받아 그래프를 초기화합니다.
각 정점에 대한 인접 리스트를 생성하고, 무방향 그래프의 특성에 따라 두 방향으로 간선을 추가합니다.

DFS와 BFS 구현:

DFS는 재귀적 방법으로 구현하여 깊이 우선으로 탐색하며, BFS는 큐를 사용하여 너비 우선으로 탐색합니다.
두 방법 모두 방문한 정점을 기록하여 중복 방문을 방지합니다.

 

결과 출력:
각 탐색의 결과를 문자열 형태로 저장하여 출력합니다.