[백준/JAVA] 2606번: 바이러스

🔺 문제

2606번: 바이러스

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static ArrayList<Integer>[] A;
    static int[]     parent;
    static boolean[] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        
        A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        parent = new int[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            parent[i] = i;
        }
        
        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());
            
            A[a].add(b);
            A[b].add(a);
        }
        
        BFS(1);
        
        int cnt = 0;
        for(int p : parent) {
            if(p == 1) {
                cnt++;
            }
        }
        System.out.println(cnt - 1);    // 1 컴퓨터 제외
    }
    
    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b) parent[b] = a;
    }
    static int find(int n) {
        if(n == parent[n]) return n;
        return parent[n] = find(parent[n]);
    }
    
    static void BFS(int n) {
        visited[n] = true;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(int next : A[now]) {
                if(!visited[next]) {
                    visited[next] = true;
                    union(now, next);     // 연결
                    queue.add(next);
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ DFS / BFS
- 인접 리스트와 유니온파인드를 사용해주었다..!

 

---

🔺 다른 풀이들

- 그래프 인접 행렬 map[][] 을 만들어 해결하셨다.

& 1과 연결된 컴퓨터 수 카운트 하는 로직을 DFS / BFS 메소드 안에 정의해주셨다.

[백준] 2606번: 바이러스(DFS, BFS)

 

---

💬 느낀 점

우와 25분만에 혼자 풀었다!!

유니온파인드 잠깐 헷갈려서 메소드 확인하고 오긴 했고

유니온 파인드 쓰지 않고도 해결할 수 있는 문제인 걸 깨달았지만....ㅎㅎ

그래도!! 뿌듯!

 

1회독	2회독	3회독	4회독	5회독
V	6.11	24.1.1

 

 

( + 6.11 2회독)

bfs로 풀었다 (방문 순서 : 2 → 5 → 3 → 6)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int cnt = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        
        A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        visited = new boolean[N + 1];
        
        while(M --> 0) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            
            A[s].add(e);
            A[e].add(s);
        }
        
        bfs(1);
        System.out.println(cnt);
    }
    
    private static void bfs(int num) {
        visited[num] = true;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(int next : A[now]) {
                if(!visited[next]) {
                    visited[next] = true;
                    queue.add(next);
                    cnt++;
                }
            }
        }
    }
}

 

 

( + 24.1.1 3회독)

DFS로 풀었다.

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
 
    static ArrayList<Integer>[] A;
    static boolean[] visited;
 
    static int cnt = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        
        A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        visited = new boolean[N + 1];
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            A[a].add(b);
            A[b].add(a);
        }
        
        dfs(1);        
        System.out.println(cnt);
    }
    
    private static void dfs(int num) {
        visited[num] = true;
        
        for(int x : A[num]) {
            if(visited[x])  continue;
            
            cnt++;
            dfs(x);
        }
    }
}