[백준 JAVA] 1260 DFS와 BFS

1260 DFS와 BFS

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

문제설명

그래프를 입력받아 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 수행한다

접근방식

O(N log N + M) 시간복잡도

 

정렬

• 각 정점의 인접 리스트를 정렬하는 데 O(E log E) 시간이 소요된다. 여기서 E는 각 정점에 연결된 간선 수이다.
• DFS
  • DFS의 시간복잡도는 O(N + M)이다.
  • 여기서 N은 정점의 수, M은 간선의 수이며, 각 정점과 간선을 각각 한 번씩 방문한다.

• BFS
  • BFS의 시간복잡도도 O(N + M)이다.
  • 각 정점과 간선을 각각 한 번씩 방문한다.

 

인접 리스트를 사용하여 그래프를 표현하고, DFS와 BFS를 각각 O(N + M) 시간복잡도로 수행하여 결과를 출력한다.

정렬에 드는 추가 시간 O(E log E)를 고려하면 전체 시간복잡도는 O(N log N + M) 이다.

 

문제 조건 분석 과정

 

• 입력 처리 및 그래프 생성
  
  • 정점 수(N), 간선 수(M), 시작 정점(V) 입력받는다
  • 정점들을 저장하기 위해 ArrayList를 사용한 인접 리스트를 생성한다.
  • 간선 정보를 읽어들여 그래프의 양방향 간선 정보를 추가한다
• DFS(깊이 우선 탐색)
  • DFS를 구현하기 위해 Stack을 사용한다
  • 스택에 시작 정점을 넣고, 노드를 하나씩 꺼내어 방문 처리한다
  • 인접 노드들은 작은 번호부터 처리되도록 역순으로 스택에 추가한다
• BFS(너비 우선 탐색)
  • BFS를 구현하기 위해 Queue를 사용한다
  • 큐에 시작 정점을 넣고, 노드를 하나씩 꺼내어 방문 처리한다
  • 인접 노드들은 큐에 순차적으로 추가한다

 

전체코드

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;

public class Main {
    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()); //시작 정점

        //그래프를 인접 리스트에 담음
        List<Integer>[] graph = new ArrayList[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++) {
            //Stack은 후입선출 구조기 때문에 나중에 들어간 노드 (작은 숫자) 가 먼저 처리됨
            Collections.sort(graph[i]); //오름차순으로 정렬
        }

        //DFS visited 배열
        boolean[] visited = new boolean[N + 1];
        List<Integer> dfsResult = new ArrayList<>();
        dfs(graph, V, visited, dfsResult);

        //BFS 결과 배열
        List<Integer> bfsResult = new ArrayList<>();
        bfs(graph, V, bfsResult);

        //DFS 결과
        System.out.println(dfsResult.stream().map(String::valueOf).collect(Collectors.joining(" ")));
        //BFS 결과
        System.out.println(bfsResult.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }

    private static void dfs(List<Integer>[] graph, int start, boolean[] visited, List<Integer> result) {
        //Stack을 사용하여 DFS 수행
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            //노드가 아직 방문하지 않았을 경우
            if (!visited[node]) {
                visited[node] = true; //방문처리
                result.add(node);
                //인접 노드 스택 추가 (역순으로 추가 = 작은 번호 먼저 탐색)
                for (int i = graph[node].size() - 1; i >= 0; i--) {
                    int neighbor = graph[node].get(i);
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

    private static void bfs(List<Integer>[] graph, int start, List<Integer> result) {
        boolean[] visited = new boolean[graph.length];
        //큐를 사용하여 BFS 수행
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);
            //인접 노드들을 큐에 추가
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}