백준 2606 (DFS)

2606번: 바이러스

과정

• 한 컴퓨터 기준 연결되어있는 모든 컴퓨터를 조사하는 느낌으로 저번에 풀었던 배추벌레? 문제랑 비슷한 것을 느꼈다.
• 그래서 DFS로 계획을 세웠다.

코드

처음에는 이렇게 작성했는데, 터미널을 보면, 2번 컴퓨터와 연결된 컴퓨터 개수가 1개라고 찍힌다.

그 이유는 main에서 시작 컴퓨터 벡터에만 연결상태를 입력했기 때문이다.

 

#include <iostream>

#include <vector>

using namespace std;

int node = 0;           // 컴퓨터 수

int edge = 0;           // 컴퓨터 쌍 개수

int answer = 0;         // 바이러스에 감염된 컴퓨터 개수

bool isvisted[101];     // 해당 인덱스에 해당하는 컴퓨터에 접근했는지 확인

vector<vector<int>> computer(101);

void DFS(int num)

{

    //cout << num << ":" << computer[num].size() << "\n";

    isvisted[num] = true;

    for(int i : computer[num])

    {

        if (isvisted[i] == false)

        {

            answer++;

            DFS(i);

        }

    }

}

int main()

{

    cin >> node;

    cin >> edge;

    for(int i = 0; i < edge; i++)

    {

        int start_node = 0;

        int end_node = 0;

        cin >> start_node >> end_node;

        computer[start_node].push_back(end_node);

        computer[end_node].push_back(start_node);

    }

   

    DFS(1);

    cout << answer;

    return 0;

}

 

• main에서 시작컴퓨터와 끝나는 컴퓨터 모두 연결을 해주었다.
• 그러다 보니, 해당 컴퓨터에 방문했다는 것을 원래는 연결을 끊으면서(원소값을 0으로 만들면서) 표현했는데, 이러니까 segmentation fault가 생긴다.(잘못된 접근)
• 그래서 isvisited라는 bool형 배열로 해당 컴퓨터에 접근했는지 확인하고 접근하지 않았으면 그 컴퓨터에 대해서도 DFS를 실행했다.
• 또한, 나같은 경우, answer(감염된 컴퓨터 개수)를 DFS의 조건문안에 넣어서 1번 컴퓨터는 자동으로 들어가지 않도록 설계했다.