백준 | 2606. 바이러스 (DFS)

dfs 연습하는 목적으로 선택한 문제

 

dfs흐름을 짰을 때 이런 느낌으로 가도록 했다.

#include <iostream>
#include <vector>
using namespace std;

void dfs(const vector<vector<int>>& vec, vector<bool>& visit, int st, int& ans) {
// 외부 함수 만들 때 vector나 int값이 변한거를 계속 반영하고 싶으면 &참조자 붙이기
    visit[st] = true;
    // 방문했는지 유무 체크 이미 방문한 경우는 pass할 수 있도록 true표시해주기
    
    for (int node : vec[st]) {
    // vec[st] 안에 있는 node들에 하나씩 방문하기
        if (!visit[node]) {
        // 방문하지 않은 노드를 만날경우
            ans++;
            // 바이러스 감염 개수를 ++하고
            dfs(vec, visit, node, ans);
            // dfs실행해서 vec[node]로 넘어가기(위의 그림 참조)
        }
    }
} 
/* return 조건은 달지 않아도 
vec[node]가 empty거나 이미 다 방문해서 dfs를 더 실행할 수 없을 경우 자동으로 종료됨. */

int main() {
    int N, linked;
    int a, b;
    cin >> N >> linked;

    vector<vector<int>>vec(N+1); // 연결쌍 입력할 vector
    vector<bool>visit(N+1, false); // 방문 유무 체크할 vector

    while(linked--){
        cin >> a >> b;
        vec[a].push_back(b);
    }

    int ans =0;
    dfs(vec, visit, 1, ans);
    cout << ans << endl;
    return 0;
}

 

이렇게 하면 제대로 실행이 되는데 왜 백준에서는 틀렸다고 나올까

while(linked--){
        cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }

 

연결된걸 입력받는 부분을 수정했다!

이게 만약에 입력을 

5 1

1 3

2 4 

이런식으로 받았을 때 단방향으로 입력을 하게되면

1  2  3  4  5

3  4          1

이렇게 되니까 1부터 탐색을 시작했을 때 1 -> 3 하고 끝나버려서 5를 놓친다

그래서 양방향으로 입력을 받아서 

1  2  3  4  5

5  4  1  2  1

3

이렇게 만들어야 모든거를 다 탐색하는것이 가능한거!!!!

그래서 이런 linked 된거를 탐색할 때는 양방향으로 입력을 받아줘야한다