[BAEKJOON] - 1260번 : DFS와 BFS

1260번 문제 링크

⌛ 시간 복잡도

• 시간 제한 : 2초 (2억회)
• node(1,000), edge(10,000)
• DFS와 BFS를 사용하더라도 충분한 연산속도 보장.

📜 로직

• DFS 구현은 쉬웠지만, BFS 개념은 처음 접해봤기 때문에, 내용을 정리하겠습니다.

1. 그래프 값을 인접 리스트에 초기화 및 방문 배열 초기화
2. 시작점의 방문 배열에 방문을 표시한 뒤 큐에 삽입한다.
3. 시작점을 큐에서 빼낸 뒤 시작점의 인접노드를 확인하여 방문여부를 확인, 방문하지 않은 경우 방문 표시 후 큐에 삽입한다.
4. 큐가 비어질 때까지 3번 과정을 반복한다.

⚠️ 주의할 점

• 위 문제에서 정점이 여러 개인 경우에 정점 번호가 작은 것을 먼저 방문하도록 구현하라는 말이 있기 때문에, 탐색 전 인접 리스트들을 오름차순으로 정렬해줘야 합니다.

Collections.sort(Collection<?> collection);

😀 성공

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

public class Main{
    static ArrayList<Integer>[] arr;
    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()); // 시작점
        
        arr = new ArrayList[n+1];
        
        for(int i=1; i <= n; i++){
            arr[i] = new ArrayList<Integer>();
        }
        
        for(int i=0; i < m ; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
            arr[e].add(s);
        }
        
        br.close();
        
        for(int i=1; i <= n; i++){
            Collections.sort(arr[i]);
        }
        
        visited = new boolean[n+1];
        dfs(v);
        sb.append("\n");
        Arrays.fill(visited,false);
        bfs(v);
        
        System.out.print(sb);
    }
    
    static void dfs(int node){
        sb.append(node).append(" ");
        visited[node] = true;
        
        for(int sub : arr[node]){
            if(!visited[sub]){
                dfs(sub);
            }
        }
    }
    
    static void bfs(int node){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        visited[node] = true;
        
        while(!queue.isEmpty()){
            int nowNode = queue.poll();
            sb.append(nowNode).append(" ");
            for(int sub : arr[nowNode]){
                if(!visited[sub]){
                    visited[sub] = true;
                    queue.add(sub);
                }
            }
        }
    }
}