문제

• 1 ~ n 번재 사람의 관계 정보를 인접행렬로 주어집니다. 두 사람이 연결되어 있으면 서로 친구입니다.
• m개의 시나리오가 있고, 각 시나리오의 최초 감염자는 2명씩 주어집니다.
• i번째 사람의 친구들 중 감염자가 2명이상이면 i번째 사람도 감염자가 됩니다.
• 각 시나리오 마다 총 감염자의 수를 구하시오.
• n(1 <= n <= 500) 학생 수, m(1 <= m <= 100) 시나리오 수
• 시간 제한 1초
• 문제 링크

---

접근 과정

1. BFS

• 문제를 보고 바로 떠오르는 생각은 BFS
  1) 최초 감염자를 큐에 넣고 너비 우선 탐색을 하면서 친구들의 감염자 친구 정보를 증가시켜줍니다.
  2) i번째 사람의 친구들 중 감염자가 2명이상이면, i번째 사람을 큐에 넣고 총 감염자를 1 증가시켜줍니다.
  3) 큐가 빌때 까지 1), 2) 수행

2. 출력 방식

• 시나리오의 마지막 케이스를 출력할때 " " 공백을 붙이면 틀렸다고 나와서, 마지막 케이스의 경우 " "를 출력하지 않았습니다.(보통 맞게 해주...)

// 3. 시나리오 결과 출력
// 각 시나리오의 마지막 케이스에 " "를 붙이면 틀렸다고 나온다.
    if(m>0) printf("%d ", cnt);
    else printf("%d \n", cnt);

• 사실 문제 자체는 어렵지 않은데, 정답률이 낮은 이유는 출력방식 때문이라고 생각합니다.

3. 시간 복잡도 계산

• 1) O(mn^2) = 시나리오 m개 * 인접행렬 n^2 완전탐색 O(n^2)

• n(1 <= n <= 500) 학생 수, m(1 <= m <= 100) 시나리오 수 이기 때문에 O(mn^2)은 O(100 500 500) = O(2천5백만) 문제의 시간 제한이 3초 이기 때문에 시간안에 풀 수 있습니다.

코드

1. C++

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

#define max_int 101
using namespace std;

//시간 복잡도: O(mn^2)
//공간 복잡도: O(n^2)
//사용한 알고리즘: BFS
//사용한 자료구조: 인접 행렬


int t, n, m, v1, v2, cnt;
// 그래프의 정보를 담을 인접 행렬 a
int a[max_int][max_int];
// ind[i] = i번째 사람의 친구들 중 감염된 사람의 수
int ind[max_int];
// check[i] = i번째 사람을 검사했는지 여부 체크
bool check[max_int];

int main(){
    scanf("%d", &t);
    for(int test_case=1; test_case<=t; test_case++){
        scanf("%d", &n);

        // 1. 그래프의 정보를 인접행렬에 받는다.
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                scanf("%d", &a[i][j]);
            }
        }

        // 2. 시나리오 수행
        scanf("%d", &m);
        while(m--){
            // 최초 발병자를 입력받는다.
            scanf("%d %d", &v1, &v2);

            // 최소 환자의 수는 2명
            cnt = 2;

            // 배열 초기화
            memset(ind, 0, sizeof(ind));
            memset(check, false, sizeof(check));

            // 최초 발병자를 큐에 넣는다.
            check[v1] = true;
            check[v2] = true;
            queue<int> q;
            q.push(v1);
            q.push(v2);

            // BFS를 통해 친구 탐색
            while(!q.empty()){
                int node = q.front();
                q.pop();

                // 인접행렬 탐색
                for(int i=1; i<=n; i++){
                    // i번째 사람이 node의 친구이고
                    if(a[node][i] == 1){
                        int next = i;
                        ind[next]++;
                        // i번째 사람의 친구들 중 2명 이상이 감염되었으면
                        if(ind[next] >= 2 && !check[next]){
                            // i번째 사람도 전염병에 걸린다.
                            cnt++;
                            check[next] = true;
                            // 큐에 넣어준다.
                            q.push(next);
                        }
                    }
                }
            }

            // 3. 시나리오 결과 출력
            // 각 시나리오의 마지막 케이스에 " "를 붙이면 틀렸다고 나온다.
            if(m>0) printf("%d ", cnt);
            else printf("%d \n", cnt);
        }
    }
}