[C언어] 백준 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

 

DFS 기초 문제인 현재 노드에서 다음 노드가 이어져 있을 경우 다음 노드로 이동 후

방문한 노드 수 만큼 출력하는 문제입니다.

 

void    init(void)
{
    int n1, n2;
    c = (int **)malloc(sizeof(int *) * m);
    visited = (int *)malloc(sizeof(int ) * m);
    for(int i = 0; i < m; i++)
        c[i] = (int *)malloc(sizeof(int) * m);
    for(int i = 0; i < m; i++)
    {
        visited[i] = 0;
        for(int j = 0; j < m; j++)
            c[i][j] = 0;
    }
    for(int i = 0; i < t; i++)
    {
        scanf("%d %d", &n1, &n2);
        // 노드들이 서로 이어져 있기에 양방향 카운트
        c[n1][n2] = 1;
        c[n2][n1] = 1;
    }
}

입력받은 c배열과 방문 체크를 위한 visited 배열을 초기화 하는 init 함수입니다.

n1, n2를 입력받고 서로 연결된걸 인식하게끔 양방향 모두 1로 초기화 해줍니다.

 

void    dfs(int cur)
{
    for (int i = 1; i < m; i++)
    {
        // 현재 노드와 i노드가 이어져 있으면서 i노드를 방문한 적이 없는 경우
        if (!visited[i] && c[cur][i])
        {
            visited[cur] = 1;
            visited[i] = 1;
            result++;
            dfs(i);
        }
    }
}

dfs 함수 호출 전에 출발 노드가 1이기에 1을 먼저 방문했다고 처리를 하고 dfs함수에 들어갑니다.

for문으로 1부터 입력받을 수 있는 최대 정수까지 반복해 줍니다.

 

현 노드에서 다음 노드가 이어져 있고 다음노드를 아직 방문하지 않았다면

카운트를 하며 함수를 다음 노드를 기준으로 재귀 호출해줍니다.

 

void    free_vis_c(void)
{
    for(int i = 0; i < m; i++)
        free(c[i]);
    free(c);
    free(visited);
}

동적 할당 해준 애들을 해제해줄 함수입니다.

 

int main(void)
{
    scanf("%d %d", &m, &t);
    m++;
    init();
    visited[1] = 1;
    dfs(1);
    printf("%d\n", result);
    free_vis_c();
    return (0);
}

마지막으로 main함수 입니다.

m과 t를 입력받습니다.

m++을 한 이유는 인덱스는 0부터 시작하죠? 하지만 저희가 입력받는 수들은 1부터 시작해서

일부러 따로 1을 더해주었습니다.(사실 더하지 않고 탐색할 때 - 1을 주면 됩니다만 그러면 코드가 길어져서 1을 더했습니다)

 

init함수를 호출해서 사용할 변수들을 초기화 해주고 출발 노드는 1이기에

1을 방문 처리한 후 dfs함수를 호출합니다.

 

dfs함수가 끝나고 출력후 동적할당을 해제하고 프로그램이 종료되게 했습니다.

 

 

dfs의 기초문제이니까 꼭 한번씩 풀어보시기 바랍니다!

 

 

반응형

전체 코드

#include <stdio.h>
#include <stdlib.h>

int m, t, **c, *visited, result = 0;

void    init(void)
{
    int n1, n2;
    c = (int **)malloc(sizeof(int *) * m);
    visited = (int *)malloc(sizeof(int ) * m);
    for(int i = 0; i < m; i++)
        c[i] = (int *)malloc(sizeof(int) * m);
    for(int i = 0; i < m; i++)
    {
        visited[i] = 0;
        for(int j = 0; j < m; j++)
            c[i][j] = 0;
    }
    for(int i = 0; i < t; i++)
    {
        scanf("%d %d", &n1, &n2);
        // 노드들이 서로 이어져 있기에 양방향 카운트
        c[n1][n2] = 1;
        c[n2][n1] = 1;
    }
}

void    free_vis_c(void)
{
    for(int i = 0; i < m; i++)
        free(c[i]);
    free(c);
    free(visited);
}

void    dfs(int cur)
{
    for (int i = 1; i < m; i++)
    {
        // 현재 노드와 i노드가 이어져 있으면서 i노드를 방문한 적이 없는 경우
        if (!visited[i] && c[cur][i])
        {
            visited[cur] = 1;
            visited[i] = 1;
            result++;
            dfs(i);
        }
    }
}

int main(void)
{
    scanf("%d %d", &m, &t);
    m++;
    init();
    visited[1] = 1;
    dfs(1);
    printf("%d\n", result);
    free_vis_c();
    return (0);
}