[JAVA] 백준 1260_DFS와 BFS

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

📌 문제 탐색하기

DFS, BFS 문제로 ,,, 그래프 탐색 문제 입니다.
방문된 점을 출력하라고 했으니 순서가 중요한 문제입니다. 

 

 

📌 가능한 시간복잡도

가능한 시간복잡도는 입력받은 정점의 개수 N ,간선의 개수 M으로 ...정점과 간선을 한번씩 탐색해서
BFS , DFS 모두 동일하게 O(N+M) ,리스트에 간선 정보를 넣고 정렬해야하니까 O(M logM)
따라서 가능한 시간복잡도는 모두 더한값 O(N+M) + O(M logM) 입니다. 

📌 코드 설계하기

그래프는 List<List<Integer>> 으로 인접 리스트를 사용하고 DFS는 스택 ,BFS는 큐를 사용해서 구현하면 된다. 

 

📌 정답 코드

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

public class Main {

    static boolean[] visited;
    static ArrayList<Integer>[] graph;




    public static void dfs(int v) {
        visited[v] = true;
        System.out.print(v + " ");
        for (int next : graph[v]) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }
    
    
    public static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        visited[v] = true;
        queue.offer(v);

        while (!queue.isEmpty()) {
            int now = queue.poll();
            System.out.print(now + " ");
            for (int next : graph[now]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
    }




    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]; // 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]);
        }
        
        visited = new boolean[N + 1];
        dfs(V);
        System.out.println();
       
        visited = new boolean[N + 1];
        bfs(V);
        System.out.println();
    }
}