16. codeup 4503 : 바이러스 문제 해결

<출처> 코드업 사이트

이번 글에서는 최단 경로 문제집 안에 있는 바이러스라는 문제를 해결해보도록 하겠습니다. 

 

알고리즘 설계는 다음과 같이 하였습니다. 함수를 재귀적으로 호출하여 전파되어 있는 컴퓨터의 수를 찾는 방식입니다.

 

코드는 다음과 같습니다

#include <stdio.h>
#include <stdbool.h>

bool a[1000][1000];     //컴퓨터 정보 배열
bool visited[1000];     //방문 정보 배열
int cnt = 0;

void f(int start, int comcnt) {     //함수
    visited[start] = true;       //방문 정보 확인
    cnt++;                //카운트 증가

    for (int i = 1; i <= comcnt; i++) {      //컴퓨터의 수만큼 탐색
        if (a[start][i] && !visited[i]) {      //호출 조건
            f(i, comcnt);                  //재귀 호출
        }
    }
}

int main() {
    int comcnt,concnt;
    scanf("%d",&comcnt);      //컴퓨터 수 입력

    scanf("%d",&concnt);         //연결 수 입력

    for (int i= 0; i <concnt; i++) {     //연결 정보 입력
        int com1, com2;
        scanf("%d %d", &com1, &com2);
        a[com1][com2] = true;     //연결정보 저장
        a[com2][com1] = true;     //연결정보 저장
    }

    f(1, comcnt); //함수 호출

    printf("%d",cnt-1);   //전파 수 출력

}

 

 

처음에 컴퓨터의 연결 정보를 저장하는 배열을 100x100 사이즈로 선언하였더니 테스트 케이스 4번에서 막혔습니다. 그래서 이것을 데이터 저장 공간의 부족이라고 생각하여 배열을 1000x1000으로 변경하였더니 문제가 해결되었습니다. 

 

글을 읽어주셔서 감사합니다.