포스트

DFS와 BFS(1260)

게시
By Kim Jung Wook 2 분읽는 시간

DFS와 BFS(1260)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

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

public class Main{
    
  static String DFS = "";
  static String BFS = "";
  
  static boolean[][] arr;
  static boolean[] visited;
  
  static Deque<Integer> deque = new ArrayDeque<>();
  
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());
    
    arr = new boolean[n+1][n+1];
    visited = new boolean[n+1];
    
    for(int i = 0; i < m; i++){
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      
      arr[a][b] = true;
      arr[b][a] = true;
    }
    
    DFS(v, n);
    Arrays.fill(visited, false);
    deque.clear();
    BFS(v, n);
    
    sb.append(DFS).append("\n").append(BFS);
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  
  public static void DFS(int start, int n){
      
    deque.offerFirst(start);
    
    while(!deque.isEmpty()){
      int num = deque.pollFirst();
      
      if(visited[num]) continue;
      
      visited[num] = true;
      DFS += num + " ";
      
      for(int i = n; i >= 1; i--){
        if(arr[num][i]){
          deque.offerFirst(i);
        }
      }
    }
  }
  
  public static void BFS(int start, int n){
      
    deque.offerFirst(start);
    
    while(!deque.isEmpty()){
      int num = deque.pollLast();
      
      if(visited[num]) continue;
      
      visited[num] = true;
      BFS += num + " ";
      
      for(int i = 1; i <= n; i++){
        if(arr[num][i]){
          deque.offerFirst(i);
        }
      }
    }
  }
}

풀이과정

  1. DFS(깊이우선탐색)과 BFS(넓이우선탐색)에 대한 개념부터 공부하였다.
  2. 개념에 대해 공부하다보니 남들이 구현해 놓은 코드도 참고하게 되었다.
  3. 그래서 풀이자체에 큰 어려움은 없었다.
  4. 처음에는 DFS는 Stack으로 BFS는 Que로 풀었다.
  5. 메모리 26988 KB / 시간 380 ms 이 나왔다.
  6. Stack과 Queue를 사용할 수 있는 Deque를 사용하여 마무리하였다.
1
2
3

- 성공
- 메모리 : 25952 KB
- 시간 : 312 ms

보안점

  1. DFS와 BFS의 활용법에 대해 좀 알아봐야할 것 같다
알고리즘, 문제
알고리즘문제