1260 JAVA DFS와 BFS

🌱 문제

1260번: DFS와 BFS

 

🌱 해결과정

1. DFS 와 BFS의 개념을 공부한 이후

2. 그에 맞는 코드를 작성했다.

---

🌱 DFS (깊이 우선 탐색)

재귀를 하기 때문에 BFS 보다 느린 것이 특징

BFS와 달리 어떤 노드를 방문했는지 여부를 반드시 검사

시간 복잡도

LinkedList : O(N + E), N: 정점수, E: 간선 수

행렬: O(N^2)

 

 

🌱 BFS (너비 우선 탐색)

최단 경로, 임의의 경로를 찾고 싶은 경우 

재귀 X, Iteration O

큐를 사용하기 때문에 FIFO (First Input First Output)

시간 복잡도 

O(N^2)

 

 

🌱 DFS & BFS  문제 차이점

DFS

모든 친구 관계를 다 살펴보는 경우

 

BFS

고정된 값과 가까운 관계부터 탐색

 

728x90

---

🌱 코드

import java.io.*;
import java.util.*;
public class Main {
    static int n; // 정점
    static int m; // 간선
    static int v; // 탐색을 시작할 정점의 번호
    static int[][] arrays;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()){
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
        }

        arrays = new int[n + 1][n + 1];
        for (int i = 0; i < m ; i ++){
            String line = br.readLine();
            st = new StringTokenizer(line);
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arrays[x][y] = 1;
            arrays[y][x] = 1;
        }

        visited = new boolean[n + 1];
        dfs(v);
        System.out.println();

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

    private static void dfs(int a) {
        visited[a] = true;
        System.out.print(a + " ");
        for (int i = 1; i < n + 1; i++){
            if(!visited[i] && arrays[a][i] == 1){
                dfs(i);
            }
        }
    }

    private static void bfs(int a) {
        Deque<Integer> queue = new LinkedList<>();
        queue.add(a);
        visited[a] = true;
        while(!queue.isEmpty()){
            int k = queue.remove();
            System.out.print(k + " ");
            for (int i = 1; i < n + 1; i ++){
                if(!visited[i] && arrays[k][i] == 1){
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}