바이러스(2606)

바이러스(2606)

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

public class Main {
  
  static boolean[][] link;
  static boolean[] visited;
  static int cnt;
  
  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();
    
    int n =  Integer.parseInt(br.readLine()), m = Integer.parseInt(br.readLine());
    
    link = new boolean[n+1][n+1];
    visited = new boolean[n+1];
    
    for(int i = 0; i < m; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken()); 
      link[a][b] = true;
      link[b][a] = true;
    }
    
    visited[1] = true;
    
    DFS(1);
    sb.append(cnt);
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static void DFS(int start) {
    for(int i = 1; i < visited.length; i++) {
      if(link[start][i] && !visited[i]) {
        visited[i] = true;
        cnt++;
        DFS(i);
      }
    }
  }
}

풀이과정

1. DFS 알고리즘을 이용하여 문제를 풀었다.

- 성공
- 메모리 : 14276 KB
- 시간 : 128 ms

보안점

1. DFS를 풀 때, stack으로 풀까, 재귀로 풀까 고민을 하다가 재귀로 풀려고 하였다
2. 재귀에 대해 로직을 구현하려고 하니 머리속에 딱 생각이 들지 않았다.
3. DFS와 BFS에 대해 더 확실히 공부해야겠다.