프로그래머스 - 네트워크 #DFS/BFS

간단하게 DFS 후 연결 요소의 개수 구하면 된다.

이 때 연결 요소를 구하는 방법은 두가지가 있는데,
main 안에서 for문을 이용해 구하거나,
함수를 만들어 구하는 방법이다.
큰 차이는 없다.

주의할 점은 벡터를 이용해 인접리스트 만들 때,
2차원 벡터를 사용해야 한다는 점.
해당 노드에 연결된 노드를 모두 저장해야 하기 때문이다.

함수 만들어서 구하기

• 탐색을 하는 dfs 함수를 만들고 이를 모든 시작점에서 호출해서 components의 개수를 세는 함수를 만들면 된다.

void dfs(int curr){	// curr : 현재 위치
	visited[curr] = true;	// dfs 들어온 순간 방문했기에 true
    for(int next : vec[curr]){	// for-each 이용, vec[curr]에 저장된 모든노드 방문
    if(!visited[next]){	// 방문한 노드가 아니라면
    	dfs(next);		// 그 노드부터 다시 dfs로 탐색
    }
}

void dfsForComponents(int curr){	// curr : 현재 위치
	int components = 0;	// components의 개수 세기 시작
    fill(vec.begin(), vec.end(), false);	// visited 초기화
    
    for(int i=0;i<N;i++){	// 모든 노드에서 실행
    	if(!visited[i]){	// 방문하지 않은 노드이면
        	dfs(i);	// dfs 탐색.
            components++;	// dfs 더 진행 안된 것은 끊겨있다는 뜻이기에 components 추가
        }
    }

}

전체 코드

#include <string>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
bool visited[201];
int N;
vector<vector<int> > vec;

void dfs(int curr){
    visited[curr] = true;
    for(auto next: vec[curr]){
        if(!visited[next]){
            dfs(next);
        }
    }
}

int dfsForComponents(int curr){
    memset(visited,false,sizeof(visited));
    int components = 0;
    for(int i=0;i<N;i++){
        if(!visited[i]){
            dfs(i);
            components++;
        }
    }
    return components;
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    N=n;
    vec.resize(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j) continue;
            
            if(computers[i][j]==1){
                vec[i].push_back(j);
                vec[j].push_back(i);
            }
        }
    }
    answer = dfsForComponents(0);
    return answer;
}