[백준] 2606번 - 바이러스 (Java)(◎)

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

2606번: 바이러스

 

<문제 분석>

1. 컴퓨터 번호가 정점, 네트워크가 간선이다.

2. 바이러스가 감염되는 컴퓨터의 수는 간선을 통해 방문할 수 있는 정점의 수와 일치한다.

3. 1번 정점부터 dfs로 탐색을 해서 마지막에 카운팅한 수를 출력하면 된다.

4. 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력이니까 1번 컴퓨터는 카운팅하면 안된다.

 

 

<문제 풀이>

1. 인접배렬로 입력값을 저장하고, 배열번호는 정점의 번호와 동일하게 1~N까지 사용하자. 무방향이므로 양쪽 방향 다 입력 받아야 한다.

2. dfs 파라미터는 다음 방문할 정점 번호를 넘겨주자.

3. dfs 종료조건은 모든 정점을 다 방문했을 때

4. dfs 스킵 조건은 탐색한 정점이 이미 방문했을 경우 / 간선이 없을 경우

 

 

<코드 구현>

import java.util.*;

/*
백준 2606번 : 바이러스
*/

public class Main {

    int N;
    int M;
    int A[][];
    boolean visited[];
    
	void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();

        // 무방향 그래프를 표현하기 위해 vertex 배열 사용
        A = new int[N+1][N+1];
        for (int i=0; i<M; i++) {
            int s = in.nextInt();
            int e = in.nextInt();
            A[s][e] = 1;//양방향 모두 값 삽입
            A[e][s] = 1;
        }
	}

    int count = 0;
    void DFS(int v) {
        visited[v] = true;
        //System.out.print(v+" ");
        for (int i=1; i<=N; i++) {
            if (visited[i]) continue;//방문한 정점이면 스킵
            if (A[v][i] == 0) continue;//값이 0이면 간선이 없으므로 스킵
            count++;
            DFS(i);
        }
    }

    void Solve() {
        visited = new boolean[N+1];
        DFS(1);
        System.out.println(count);
    }
	public static void main(String[] args) {
		Main m = new Main();
		m.InputData();
        m.Solve();
	}
}

 

---

 

<풀이 #2>

1. 인접리스트 방식으로 다시 풀었음.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;

public class Main {
    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    int N, M;
    boolean visited[];

    int BFS(int start) {
        Queue<Integer> Q = new LinkedList<>();
        int count = 0;
        Q.offer(start);
        visited[start] = true;

        while (!Q.isEmpty()) {
            int now = Q.poll();
            for (int next : list.get(now)) {
                if (visited[next]) continue;
                Q.offer(next);
                visited[next] = true;
                count++;
            }
        }
        return count;
    }
	int Solve() {
		int sol = 0;
        visited = new boolean[N+1];
        sol = BFS(1);
		return sol;
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        for (int i=0; i<=N; i++) {
            list.add(new ArrayList<>());
        }
        
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list.get(s).add(e);
            list.get(e).add(s);
        }
    }

    public static void main(String[] args) throws Exception {
        int ans = -2;
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        ans = m.Solve();// 여기서부터 작성
        System.out.println(ans); // 출력 하는 부분
    }
}