[구름LEVEL] 백신

난이도	정답률
★★	-%

프리미엄 알고리즘 위클리 비타알고 시즌3 1주차

구름EDU - Be Really Excellent!

문제

백신은 한 명의 환자에게 접종하면 바이러스와 유사한 방식으로 해당 사람과 밀접하게 접촉하는 사람들에게 전파되어 그 사람들까지 모두 치료한다. 매우 효과적이고 빠른 속도로 전파되지만, 제작 비용이 너무 많이 든다는 단점으로 인해 현재 프로토 타입으로 제작된 단 하나의 백신만 사용할 수 있는 상황이다.

하나의 백신을 이용하여 가장 많은 사람들을 치료하고자 할 때, 어떤 사람에게 백신을 접종해야 하는지 구해보자.

환자들의 수 N, 환자 사이 관계의 수 M

2 ≤ N, M ≤ 200,000

관계는 a b 형태로 주어지고, 두 환자가 서로 밀접하게 접촉할 수 있음을 뜻한다.

 

해결

key point, DFS또는BFS로 연결되어 있는 최대 노드 개수와 시작 노드의 번호를 구한다.

• 2차원 배열을 사용하여 관계 a, b가 주어지면 a행에 b를 추가하고 b행에 a를 추가한다.
• 1부터 N번 환자까지 확인하지 않았다면 연결되어있는 환자의 수를 센다.
• 1번 부터 i-1번까지 환자 중 연결되어있는 환자의 수가 가장 컸던 값을 maxCnt라고 하고 
• i번째 환자와 연결되어있는 환자의 수가 cnt일 때
• maxCnt < cnt 이면 maxCnt를 cnt로 갱신하고, maxNum 을 i로 갱신한다.

1번 부터 N 번 환자까지 모두 확인을 했다면,
'백신을 가장 많이 퍼뜨리기 위해 접종해야 하는 환자의 번호(maxNum)'와 '해당 환자에게 백신을 접종했을 때 치료할 수 있는 환자의 수(maxCnt)'를 출력한다.

코드

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> v;
int n, m, maxNum, maxCnt, cnt;
int chk[200005];
void dfs(int num) {
    for (auto child: v[num]) {
        if (!chk[child]) {
            cnt++;
            chk[child] = 1;
            dfs(child);
        }
    }
}
int main() {
    scanf("%d %d", &n, &m);
    v.resize(n+1);
    for (int i = 0, a, b; i < m; i++) {
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        if (!chk[i]) {
            cnt = 1;
            chk[i] = 1;
            dfs(i);
            if (maxCnt < cnt) {
                maxCnt = cnt;
                maxNum = i;
            }
        }
    }
    printf("%d %d", maxNum, maxCnt);
    return 0;
}

 

후기

나는 DFS로 풀었지만 해설을 확인하니, 1부터 N(200,000)까지 원형으로 연결된 그래프일 경우 DFS로 구현한다면 한 번의 DFS로 모든 노드를 방문할 수 있기 때문에 스택 오버플로우가 생길 가능성이 있어 BFS로 푸는게 안전하다고 한다.

재귀함수는 스택 영역의 메모리를 사용하고, 풀고 있는 문제의 스택 영역 메모리 제한이 작다면 DFS로 문제를 해결하는 것을 고려해볼 필요가 있습니다.

+ 구름 채점환경에서의 메모리 제한은 전체 메모리 영역이므로 해당되지 않는다고 한다.

 

스택 오버플로우란?

스택 포인터가 스택의 경계를 넘어설 때 일어난다. 호출 스택은 제안된 양의 주소 공간을 이루며 대개 프로그램 시작 시 결정된다.

프로그램이 호출 스택에서 이용 가능한 공간 이상을 사용하려고 시도할 때, 스택이 오버플로(overflow)된다고 하며 이 경우 일반적으로 프로그램 충돌이 발생하게 된다.