[프로그래머스] 네트워크(C++)

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

dfs 문제!

방문 노드인지 확인하는 visit 벡터를 활용하였다.

computers의 0번째 행이 1번 노드와 연결된 노드를 나타내므로,

dfs 함수에서 방문 여부를 확인할 땐 index+1로 조회해야 한다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;
vector<int>visit;
void dfs(int index,vector<vector<int>> computers)
{
    vector<int>temp=computers[index-1];
    //해당 index와 연결된 컴퓨터 탐색
    for(int i=0;i<temp.size();i++)
    {
        //연결되고, 방문하지 않은 컴퓨터 기준 탐색
        if(temp[i]==1)
        {
            if(!visit[i+1])
            {
                visit[i+1]=1;
                dfs(i+1,computers);
            }
        }
    }
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    visit= vector<int>(n+1,0); //방문시 1으로 변경
    int index=1; //방문할 컴퓨터 번호, 1번부터 시작
    for(int i=1;i<visit.size();i++)
    {
        if(!visit[i]) //방문하지 않았다면
        {
            visit[i]=1;
            dfs(i,computers);
            answer++;
        }
    }    
    return answer;
}