[프로그래머스] 네트워크 (DFS)
접근 방식
위의 그래프에서 알 수 있듯이, 그래프 문제이고 연결된 그래프의 개수를 구해야 하므로, 그래프의 연결된 노드들을 따라서 탐색하다가 연결이 끊기면 네트워크 하나가 끝난 것이므로 +1 해주며, 네트워크의 개수를 구하면 된다.
→ DFS로 그래프를 탐색!
재귀 함수 작성
우선, DFS를 구현하기 위해 재귀함수를 작성 해야한다.
1.
1번 컴퓨터부터 연결 되어 있는 것들을 탐색해나가는 dfs 함수를 호출!
2.
1번 컴퓨터와 연결되어 있는 것들을 탐색하던 도중에, 1번 컴퓨터와 2번 컴퓨터가 연결 되어 있는 것을 발견한다.
3.
그 함수 내에서 2번 컴퓨터의 탐색을 시작해야 하므로, 2번 컴퓨터를 탐색해 나가는 dfs 함수를 호출한다.
4.
2번 컴퓨터와 연결 되어 있는 것들을 탐색하던 도중에 1번 컴퓨터와 연결 되어 있는 것을 발견하지만, 이는 1번 컴퓨터를 탐색할 때 이미 수행한 것이다.
…
여기서 알 수 있는 것은, 각 컴퓨터 별로 탐색 여부를 체크하는 과정이 필요하다는 것이다.
그래고 재귀적으로 DFS 함수를 호출할 때, 탐색하는 컴퓨터의 번호가 달라지므로 DFS 함수의 매개변수로 탐색할 컴퓨터의 번호를 받아야 한다는 것을 알 수 있다.
문제에서 컴퓨터의 개수는 200개 이하라고 하였으므로, 크기 200인 배열을 선언하여 각 컴퓨터 별로 탐색여부를 체크하여 표시한다.
1.
i 번째 컴퓨터가 아직 탐색하지 않은 컴퓨터일 때, 탐색을 시작한다.
→ dfs(i) 호출
2.
i 번째 컴퓨터와 연결된 j 번째 컴퓨터가 아직 탐색하지 않은 컴퓨터일 때, 탐색을 시작한다.
→ dfs(j) 호출
3.
j 번째 컴퓨터와 연결된 컴퓨터가 없어서 j 번째 컴퓨터의 탐색이 종료 된다.
→ dfs(j) 종료
4.
dfs(j) 를 호출하였던 dfs(i) 에서 i 번째 컴퓨터의 탐색이 종료 된다.
→ dfs(i) 종료
…
이렇게 재귀적으로 호출된 함수가 모두 종료될 때가 그래프 한개가 연결된 상태이므로 answer + 1 을 해준다.
#include <iostream>
#include <vector>
using namespace std;
int check[200];
void dfs(int cur_com, int n, vector<vector<int>> computers) {
for (int i = 0; i < n; i++) {
if (check[i] == 0 && computers[cur_com][i] == 1) {
dfs(i, n, computers);
}
}
}
int solution(int n, vector<vector<int>> computers) {
int answer = 0;
for (int i = 0; i < n; i++) {
if (check[i] == 0) {
dfs(i, n, computers);
answer++;
}
}
return answer;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, data;
vector<int> v;
vector<vector<int>> computers;
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> data;
v.push_back(data);
}
computers.push_back(v);
v.clear();
}
cout << solution(n, computers);
return 0;
}
C++
복사