[코딩테스트]백준 - 바이러스(2606번)

바이러스

문제

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

예를 들어 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

출처

• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 초등부 3번
• 잘못된 데이터를 찾은 사람: djm03178 jsa3824

알고리즘 분류

• 플로이드 와샬 알고리즘

해결한 코드

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
var n = input[0] / 1
var coupleComputer = input[1] / 1

if (n <= 1){
    console.log(0)
} else {
    var networks = []
    for (var i = 2; i < input.length; i++) {
        networks.push(input[i].split(' ').map((element) => element / 1))
    }
   
    var connectedStatus = makeConnectedStatus()

    for (var i = 0; i < coupleComputer; i++) {
        var network = networks[i]
        if (!isConnected(network)) {
            connectedStatus = setConnectedStatus(network)
        }
    }

    var answer = howManyInfected(connectedStatus)
    console.log(answer)
}

function makeConnectedStatus(){
    var connectedStatus = Array(n + 1)
    for (var i = 0; i <= n; i++) {
        connectedStatus[i] = i
    }
    return connectedStatus
}

function isConnected(network) {
    var one = network[0]
    var theOhter = network[1]
    if (connectedStatus[one] !== connectedStatus[theOhter]) return false
    return true
}

function setConnectedStatus(network) {
    var checkVar = connectedStatus[network[1]]
    var resultValue = connectedStatus[network[0]]
    for (var i = 0; i < connectedStatus.length; i++) {
        if (connectedStatus[i] === checkVar) {
            connectedStatus[i] = resultValue
        }
    }
    return connectedStatus
}

function howManyInfected(connectedStatus) {
    var count = 0
    for (var i = 2; i < connectedStatus.length; i++) {
        if (connectedStatus[i] === connectedStatus[1]) count++
    }
    return count
}

풀이

※ 플로이드 와샬 알고리즘 문제로 분류되어있지만, 사실상 유니온 파인드를 사용한 것 같다.

1. 연결 상태를 확인한다.

• 일단, 어떤 컴퓨터들이 어떻게 연결되어있는지를 확인하기 위한 배열을 만든다.
  • connectedStatus 라는 배열을 만들었고,
  • 3번 컴퓨터는 3번과 연결되어있다는 의미로 connectedStatus[3] = 3 과 같이 만들어주었다.
    ※ 초기 상태는 모두 자기 자신과 연결되어있도록 설정하였다.

• 이제 컴퓨터를 연결한다.
  ex. [1, 2]가 입력되면

connectedStatus = [ 0, 1, 1, 3, 4, 5, 6, 7 ]

(참고) index 1부터 시작하므로, 0은 그냥 무시.
2가 1과 연결되었으므로 connectedStatus[2] = connectedStatus[1] 이 되었다.
ex. [2, 3]이 입력되면

connectedStatus = [ 0, 1, 1, 1, 4, 5, 6, 7 ]

3과 2가 연결되었으므로, connectedStatus[3] = connectedStatus[2] 가 되었다.
이를 통해 3이 (2와 연결되었던) 1과도 연결되었다는 것을 알 수 있다.

이런 식으로 모든 컴퓨터의 연결 상태를 확인한다.

2. 1번 컴퓨터와 연결된 컴퓨터의 갯수를 센다.

1번 컴퓨터와 연결된 상태가 같은 것들의 갯수를 세어준다.