[Baekjoon] 2606 바이러스 - JAVA

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

---

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

---

예제 입력 1 

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1 

4

 

---

📝 제출 답안

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

public class Main {
    static int map[][];
    static boolean visit[];
    static int count = 0;
    static int computer, network;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        computer = Integer.parseInt(br.readLine());
        network = Integer.parseInt(br.readLine());

        map = new int[computer+1][computer+1];
        visit = new boolean[computer+1];

        for (int i = 0; i < network; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a][b] = map[b][a] = 1;
        }

        bw.write(String.valueOf(dfs(1)));
        bw.flush();
    }

    public static int dfs(int n) {
        visit[n] = true;
        for (int i = 1; i <= computer; i++) {
            if (map[n][i] == 1 && !visit[i]) {
                count++;
                dfs(i);
            }
        }

        return count;
    }
}

 

DFS, BFS로 푸는 문제였다.

처음에는 탐색 그래프 알고리즘을 생각하지 못하고 HashMap으로 연결 여부를 찾도록 풀었더니 오답이었다.

분명 DFS, BFS 문제를 정리했었는데 아직 익숙해지지 않아서 구글링해보면서 다시 익혔다.

일단 오늘은 DFS가 좀 더 접근하기 쉬워보여서 DFS로 풀었는데, BFS로도 풀어봐야겠다.

 

 

전역 변수 설정하기

static int map[][];
static boolean visit[];
static int count = 0;
static int computer, network;

 

먼저 map[][]은 인접 행렬을 사용해서 컴퓨터 간의 연결 상태를 저장할 것이다.

예를 들어서 map[a][b] = 1이면 a와 b가 연결되어 있다는 것을 의미한다.

 

visit[]은 특정 컴퓨터 방문 여부를 저장하기 위한 배열이다. DFS 탐색에서 이미 방문한 컴퓨터는 다시 방문하지 않도록 제한해야하기 때문이다.

 

count는 컴퓨터 1번에서 시작해서 감염된 컴퓨터의 개수를 세는 변수이다.

 

compuer와 network는 각각 컴퓨터와 컴퓨터 사이를 연결하는 네트워크 연결 개수를 나타내는 변수이다.

 

 

입출력 처리하기

BufferedReader와 BufferedWriter를 통해 입출력을 받도록했다.

computer와 network 개수를 입력 받은 후

map과 visit 배열을 computer + 1 크기로 선언해준다. 컴퓨터의 번호가 1번부터 들어오기 때문에 0번째 공간은 비워두고 사용하기 위함이다.

map = new int[computer+1][computer+1];
visit = new boolean[computer+1];

 

그 후 네트워크 연결 정보를 StringTokenizer로 입력 받아 map[][]에 연결 정보를 저장한다.

for (int i = 0; i < network; i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    map[a][b] = map[b][a] = 1;
}

 

 

DFS 함수 흐름

public static int dfs(int n) {
    visit[n] = true;
    for (int i = 1; i <= computer; i++) {
        if (map[n][i] == 1 && !visit[i]) {
            count++;
            dfs(i);
        }
    }
    return count;
}

 

1. 먼저 dfs 함수가 호출되면 visit[n] 현재 노드(컴퓨터)의 방문 여부를 true로 설정해준다.

 

2. 이 후 for문을 통해 다른 모든 컴퓨터를 확인하여,

만약 현재 컴퓨터와 연결되어 있고 방문하지 않았다면 감염된 컴퓨터 수를 증가(count++)시킨다.

 

3. 그리고 dfs(i) 재귀 호출로 DFS 탐색을 이어간다.

 

4. 마지막으로 감염된 컴퓨터의 수 count를 반환해준다.

 

 

DFS 탐색 함수 호출 및 결과 출력

컴퓨터 1번을 시작점으로 DFS 탐색을 수행하여 bw.write 메서드를 통해 문자열을 출력해준다. 

해당 메서드는 문자열만 출력 가능하도록 설계되어 있어 String 변환 과정을 거친 것이다.

bw.write(String.valueOf(dfs(1)));

 

 

제출 현황