[백준 2606] 알고리즘 3^4일차 : 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

 

 

C++ DFS&BFS

이게 얼마만의 백준인가 😂 약간 그리웠음. 프로그래머스 푼다고 떠난지 12일만에 복귀

백준의 이 러프함에 길들여졌다.. (사담 그만)

 

단계별 풀이 DFS&BFS문제 중에 두번째 문제이다. 하나의 그래프를 전체 탐색하면 되는 문제

경로를 출력할 필요 없이 첫 노드를 제외한 카운트만 세어주면 된다.

 

접근방법

DFS or BFS 중에 로직이 더 간단한 DFS로 풀었고 (큐 쓰기 싫어서 그랬음 맞음)

DFS를 재귀형식으로 썼고, 인접리스트를 사용했다.

백준 문제는 아마 대부분 데이터가 커서 인접행렬을 쓸 수 있는 문제가 얼마 없을 것 같다.

하지만 본 문제는 노드가 100개로 제한돼있어서 가능할지도. 간선의 개수는 제한되어있진 않았다.

 

(풀이시간 25분)

 

*

틀리지는 않았는데 처음에 입력받는 번호 그대로 1부터 시작하는 숫자를 그대로 써서

visit배열이랑 adj에 접근하는 인덱스 부분에서 실수가 있었다.

 

 

소스코드

#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<vector<int>> adj;
bool visit[101];
int cnt = 0;
void dfs(int here){
    visit[here] = true;
    for(int i = 0 ; i < adj[here].size() ; i++){
        int next = adj[here][i];
        if(!visit[next]){
            dfs(next);
            cnt++;
        }
    }
}
int main(){
    cin >> n >> m;
    adj = vector<vector<int>>(n+1);
    int u,v;
    for(int i = 0 ; i < m ; i++){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    cout << cnt;
    return 0;
}