백준 - 바이러스(Java, Python)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/2606

[문제 설명]

간단한 그래프 탐색 문제. 

1번 노드가 포함된 그래프에 몇개의 노드가 있나 체크하면 된다.

 

시간복잡도는 최악의 경우 모든 노드의 개수(V)를  돌고, 모든 연결된 간선의 개수(E)를 체크해야하므로 O(V+E).

문제에서는 컴퓨터의 개수는 100개,

간선의 최대 개수는 100C2(모든 컴퓨터에서 두 대의 컴퓨터를 선택하는 경우)이므로 100*99/2 = 4950

총합은 5050회.

 

[Java 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        // 전체 PC 개수
        int cntOfPC = Integer.parseInt(br.readLine());
        // 그래프
        List<Integer>[] map = new LinkedList[cntOfPC];
        // 방문 여부
        boolean[] isInfected = new boolean[cntOfPC];
        // 간선 개수
        int cntOfConnectedPC = Integer.parseInt(br.readLine());

        // 그래프 그리기
        for (int i = 0; i < cntOfConnectedPC; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int point1 = Integer.parseInt(st.nextToken())-1;
            int point2 = Integer.parseInt(st.nextToken())-1;

            if (map[point1] == null) {
                map[point1] = new LinkedList<>();
            }
            map[point1].add(point2);

            if (map[point2] == null) {
                map[point2] = new LinkedList<>();
            }
            map[point2].add(point1);
        }

        // BFS 탐색
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        int cntOfCorruptedPC = 0;
        while (!queue.isEmpty()) {
            int numOfPC = queue.poll();
            // 이미 감염된 컴퓨터면 중단
            if (isInfected[numOfPC]) {
                continue;
            }
            isInfected[numOfPC] = true;
            cntOfCorruptedPC++;

            for (int i = 0; i < map[numOfPC].size(); i++) {
                int nextNode = map[numOfPC].get(i);
                if (!isInfected[nextNode]) {
                    queue.offer(nextNode);
                }
            }
        }

        System.out.println(cntOfCorruptedPC-1);
    }
}

[Python]

import queue

cntOfPC = int(input())
cntOfNetworks = int(input())
networkOfPC = []
isInfected = []
for i in range(cntOfPC):
    networkOfPC.append([])
    isInfected.append(False)
    for j in range(cntOfPC):
        networkOfPC[i].append(False)

for i in range(cntOfNetworks):
    startNumber, endNumber = map(int,input().split())
    networkOfPC[startNumber-1][endNumber-1] = True
    networkOfPC[endNumber-1][startNumber-1] = True

cntOfViruses = 0
q = queue.SimpleQueue()
q.put(0)
while not q.empty():
    noOfPC = q.get()
    if isInfected[noOfPC]:
        continue
    isInfected[noOfPC] = True
    cntOfViruses += 1
    for idx in range(len(networkOfPC[noOfPC])):
        if idx == noOfPC:
            continue
        if networkOfPC[noOfPC][idx] and not isInfected[idx]:
            q.put(idx)
print(cntOfViruses-1)

[답지들 보고 보완한 파이썬 수정 코드]

 

import sys


def recursion(num, cnt_of_viruses):
    if isInfected[num]:
        return cnt_of_viruses
    isInfected[num] = True

    for i in mapOfPC[num]:
        if not isInfected[i]:
            cnt_of_viruses = recursion(i, cnt_of_viruses + 1)
    return cnt_of_viruses


input = sys.stdin.readline
cntOfComputers = int(input())
cntOfNetworks = int(input())
isInfected = [False]*cntOfComputers
mapOfPC = [[] for _ in range(cntOfComputers)]

for _ in range(cntOfNetworks):
    a,b = map(int, input().split())
    mapOfPC[a-1].append(b-1)
    mapOfPC[b-1].append(a-1)
print(recursion(0, 0))