[Java] DFS와 BFS (Lv. Sliver2)

DFS와 BFS (Lv. Sliver2)

---

1. 문제

2. 풀이

---

1. 문제

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

 

2. 풀이

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

class Main {
    static int[][] graph;
    static boolean[] visited;
    
    public static void dfs(int V) {
        visited[V] = true;
        System.out.print(V + " ");
        
        if (V == graph.length) {
            return;
        }
        
        for (int i = 1; i < graph.length; i++) {
            if (graph[V][i] == 1 && visited[i] == false) {
                dfs(i);
            }
        }
    }
    
    public static void bfs(int V) {
        Queue<Integer> q = new LinkedList<>();
        
        q.add(V);
        visited[V] = true;
        System.out.print(V + " ");

        while (!q.isEmpty()) {
            int tmp = q.poll();
            
            for (int i = 1; i < graph.length; i++) {
                if (graph[tmp][i] == 1 && visited[i] == false) {
                    q.add(i);
                    visited[i] = true;
                    System.out.print(i + " ");
                }
            }
        }
    }
    
    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 int[N+1][N+1];
        
        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][v] = graph[v][u] = 1;
        }
        
        visited = new boolean[N+1];
        dfs(V);
        
        System.out.println();
        
        visited = new boolean[N+1];
        bfs(V);
    }
}

 

 

위의 코드로 위와 같은 형태의 트리가 존재할 때 DFS와 BFS 탐색 방식을 알 수 있습니다.

 

- DFS

현재 노드와 연결된 노드 중 방문하지 않은 노드를 재귀적으로 탐색합니다.

1 -> 2 -> 4 -> 3 -> 5 의 순서로 동작합니다.

 

- BFS

우선순위 큐를 활용해서 가까운 노드 순서대로 탐색합니다.

1 -> 2 -> 3 -> 4 -> 5 의 순서로 동작합니다.

---

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3