[BOJ] 2606 바이러스

이 글은 BOJ 2606-바이러스 문제에 대해 다루겠습니다. BFS, DFS관련 게시글은 요이따 여기에 있습니다. 공부한 것을 정리하는 형식으로 작성되었으므로 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

 

결론부터 말하자면 문제를 풀 때 DFS를 쓰는 것이 더 적합합니다. 왜냐하면 바이러스에 걸린 1번 컴퓨터와 연결된 모든 컴퓨터를 찾아야 하기 때문입니다. DFS는 모든 노드를 traverse할 때, BFS는 path finding을 할 때 잘 쓰이기 때문입니다. 그런데 저는 BFS로 풀었냐구요? 음... 약간 제가 재귀문 트라우마가 있어서 BFS로 먼저 짰다가 시간 초과나면 DFS로 갈아탈 생각이었습니다. 뭐... 코테 볼 때나 면접 볼 때 그럴 여유는 없겠지만 우리는 연습 중이니 두 코드 모두 짜도 되지 않겠습니까?

---

풀이 1 : BFS

(코드 복사를 원하시는 분은 [더보기]를 눌러주세요.)

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

using namespace std;

int main(void){
	// computers : total number of computers
   	// connections : total number of connections
    int computers, connections, comA, comB;
    int v = 1; // starting computer
    cin >> computers >> connections;
    vector<int> *ptr = new vector<int>[computers + 1]; // +1 because computer starts from 1 (not 0)
    
    for(int i = 0; i < connections; i++){
        cin >> comA >> comB;
        ptr[comA].push_back(comB);
        ptr[comB].push_back(comA); // undirected graph
    }

    queue<int> que;
    vector<int> connectedComputers;
    bool flag[computers + 1]; // +1 because computer starts from 1
    for(int i = 0; i < computers + 1; i++)
        flag[i] = false;
    
    que.push(v);
    flag[v] = true;
    vector<int>::iterator it;
    while(!que.empty()){
        v = que.front();
        connectedComputers.push_back(v);
        que.pop();
        for(it = ptr[v].begin(); it != ptr[v].end(); ++it){
            if(flag[*it] == false){
                flag[*it] = true;
                que.push(*it);
            }
        }
    }

    cout << connectedComputers.size() - 1 << endl;
    return 0;
}

결과 : 사용메모리 1984KB 맞았습니다!

---

풀이 2 - DFS

이제 한 번 제대로 풀어볼까요?ㅋㅋ 위와 코드와 비교했을 때 자잘하게 달라진 점이 몇가지가 있습니다. 사실 뭐 풀이 로직이 변한 것은 당연하지만 정답 출력 방식이라던지 자잘한 변화들이 있습니다. 스택을 쓸까 재귀문을 쓸까 하다가 빠르게 구현 가능한(저에게 dfs는 써브니까요... 사랑해 bfs...ㅋㅋ) 재귀문으로 만들어 보았습니다.

(코드 복사를 원하시는 분은 [더보기]를 눌러주세요.)

#include <iostream>
#include <vector>

using namespace std;

int answer = 0; // answer
void dfs(vector<int> *graph, int v, bool *flag){
    answer++;
    flag[v] = true;
    vector<int>::iterator it;
    for(it = graph[v].begin(); it != graph[v].end(); ++it){
        if(flag[*it] == false){
            dfs(graph, *it, flag);
        }
    }
}

int main(void){
    // computers : total number of computers
    // connections : total number of connections
    int computers, connections, comA, comB;
    cin >> computers >> connections;
    vector<int> *ptr = new vector<int>[computers + 1]; // +1 because computer starts from 1 (not 0)
    for(int i = 0; i < connections; i++){
        cin >> comA >> comB;
        ptr[comA].push_back(comB);
        ptr[comB].push_back(comA); // undirected graph
    }

    bool flag[computers + 1]; // +1 because computer starts from 1
    for(int i = 0; i < computers + 1; i++)
        flag[i] = false;
    
    dfs(ptr, 1, flag);
    
    cout << answer - 1 << endl;
    return 0;
}

결과 : 사용메모리 1984KB 맞았습니다!