Written by JS970
on March 20, 2023

2606 - 바이러스

난이도: 실버 3
날짜: 2023년 3월 20일
상태: Correct
추가 검토 여부: No
알고리즘 : DFS

Solution

그래프를 구현하여 상황을 입력받고, 입력받은 상황에 대하여 DFS탐색을 통해 인접한 노드의 수를 구하면 되는 문제이다.
아직 Graph및 DFS구현이 서툴러서 많이 틀렸다.
1260번의 DFS코드를 참고했다.
- DFS의 경우 현제 노드, 인접 리스트, 방문 확인 리스트의 입력을 필요로 한다.
- 인접 리스트의 경우 1260번과 달리 이중 벡터로 구현했다.
- dfs의 recursive 구현이 아닌 반복문을 사용한 구현에 대해 알아보자.

code

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

void dfs(int node, vector<vector<int>> adj, bool infected[])
{
    infected[node] = true;
    for(int i = 0; i < adj[node].size(); i++)
    {
        int neighbor = adj[node][i];
        if(!infected[neighbor]) dfs(neighbor, adj, infected);
    }
}

int main()
{
    int N;
    cin >> N;
    int M;
    cin >> M;

    vector<vector<int>> adj(N+1);
    bool infected[N+1] = {false};
    infected[1] = true;
    for(int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    int count = 0;
    dfs(1, adj, infected);
    for(int i = 2; i < N+1; i++) if(infected[i] == true) count++;
    cout << count << endl;
    return 0;
}

dfs 함수의 스택 구현

void dfs(int start, vector<vector<int>> adj, bool infected[])
{
    stack<int> s;
    s.push(start);

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        if (!infected[node]) {
            infected[node] = true;
            for (int i = 0; i < adj[node].size(); i++) {
                int neighbor = adj[node][i];
                s.push(neighbor);
            }
        }
    }
}

위와 같이 stack을 사용하여 recursive하지 않게 구현할 수 있다.
1260번의 DFS역시 위와 같이 구현할 수 있었다.

ref

2606번: 바이러스

1260번: DFS와 BFS 풀이

Top