[백준][Java] 2606번 바이러스

 

 

BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    
    static boolean[][] connected;
    static boolean[] checked;
    
    public static void main(String[] args) throws IOException{
        int N = Integer.parseInt(br.readLine());
        int T = Integer.parseInt(br.readLine());
        
        connected = new boolean[N+1][N+1];
        checked = new boolean[N+1];
        
        for(int i=0; i<T; i++){
            StringTokenizer stk = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            
            connected[a][b]=true;
            connected[b][a]=true;
        }
        
        System.out.println(BFS(1));
        
        
        
    }
    
    static int BFS(int start) {
        int res = 0;
        
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        
        while(!q.isEmpty()) {
            int presNum = q.poll();
            checked[presNum] = true;
            
            for(int i=1; i<checked.length; i++) {
                if(connected[presNum][i] && !checked[i]) {
                    q.offer(i);
                    checked[i]=true;
                    res++;
                }
            }
            
        }
        
        
        return res;
    }
}
 
 

 

 

 

DFS

 

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    
    static boolean[][] connected;
    static boolean[] checked;
    static int cnt;
    
    public static void main(String[] args) throws IOException{
        int N = Integer.parseInt(br.readLine());
        int T = Integer.parseInt(br.readLine());
        
        connected = new boolean[N+1][N+1];
        checked = new boolean[N+1];
        cnt=0;
        
        for(int i=0; i<T; i++){
            StringTokenizer stk = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            
            connected[a][b]=true;
            connected[b][a]=true;
        }
        
//        System.out.println(BFS(1));
        DFS(1);
        System.out.println(cnt-1);
        
        
    }
    
    static void DFS(int preNum) {
        checked[preNum]=true;
        cnt++;
        
        for(int i=1; i<checked.length; i++) {
            if(connected[preNum][i] && !checked[i]) DFS(i);
        }
        
    }
    
    
    static int BFS(int startNum) {
        int res = 0;
        
        Queue<Integer> q = new LinkedList<>();
        q.offer(startNum);
        
        while(!q.isEmpty()) {
            int presNum = q.poll();
            checked[presNum] = true;
            
            for(int i=1; i<checked.length; i++) {
                if(connected[presNum][i] && !checked[i]) {
                    q.offer(i);
                    checked[i]=true;
                    res++;
                }
            }
            
        }
        
        
        return res;
    }
}