[2606] 바이러스

문제

2606번: 바이러스

 

 

🔎 해결 방법

• dfs를 실행할때마다 count(바이러스에 감염된 컴퓨터의 수) 1 증가
• 연결 요소의 개수(cc)가 2이상이라는 것은 1번 컴퓨터와는 연결되지 않았다는 소리이므로, cc는 1일 때까지만 실행
• 마지막으로 출력할때는 count에서 1번 컴퓨터를 제외해야 하므로 1 빼고 출력

dfs와 connected components의 개념만 잘 잡혀있었으면 바로 풀 수 있었던 문제인데,

저 둘을 사용하면 된다는 것은 바로 알았지만 dfs코드가 아직 제대로 잡혀있지 않아서 고생을 좀 했다ㅎ

dfs코드를 전에도 백준에서 사용한 기억이 있어서 뒤져보니

'[11724] 연결 요소의 개수' 문제에서 dfs를 사용하여 connected components의 개수를 찾는 문제를 풀었더라ㅎㅎ

[11724] 연결 요소의 개수

 

 

💡 내 코드(C)

/*[2606] 바이러스*/
/*https://www.acmicpc.net/problem/2606*/
/*dfs가 호출된 횟수 = 바이러스에 감염된 컴퓨터의 수*/

#include <stdio.h>
int matrix[101][101];
int visit[101];
int comn; /*the number of computer*/
int linkedn, count = 0; /*number of connected computer pairs, the number of infected computer*/
void dfs(int v);

int main(void)
{
    int u, v; // two end points of the trunk line
    int cc = 0;// the number of new dfs invocations, end when count is 2
    scanf("%d", &comn);
    scanf("%d", &linkedn);
    for (int i = 0; i < linkedn; i++) {
        scanf("%d %d", &u, &v);
        matrix[u][v] = 1;
        matrix[v][u] = 1;
    }
    
    // node starts ar 1
    for(int i=1;i<comn;i++) {
    	if (!visit[1] && (cc < 2)) {
            dfs(1);
            cc++; /*number of connected components*/
        }
    }
        
    printf("%d", count - 1); /*except the initial computer*/
    return 0;
}

void dfs(int v)
{
    for (int i = 1; i <= comn; i++) {
    	if (matrix[v][i] == 1 && !visit[i]) {
            count++;
            visit[i] = 1; /*visited*/
            dfs(i);
        }
    }       
}