programming language/Algorithm
[Divide and Conquer 예제] 프로그래머스 Level3 네트워크
jellylucy
2021. 8. 25. 11:50
문제
코딩테스트 연습 - 네트워크
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있
programmers.co.kr
문제 풀이 1
네트워크의 개수는 연결되지 않는 컴퓨터들의 상황의 개수이다.
computer[i][i]에서 이동할 수 있는 컴퓨터들을 recursion으로 false로 바꾸어 준다.
solution에서, 1~n까지의 컴퓨터 개수대로 dfs를 돌리고,
각 computer[i][i]와 연결되어 있는 컴퓨터들로 이동해서 값을 false로 바꾸어 준다.
만약 마지막이 true로 끝나면 answer++ 한다.
#include <string>
#include <vector>
using namespace std;
int answer = 0;
bool dfs(vector<vector<int>>& computers, int iter){
if(!computers[iter][iter]) return false;
computers[iter][iter] = 0;
for(int i = 0;i<computers.size();i++){
if(computers[iter][i]) dfs(computers, i);
}
return true;
}
int solution(int n, vector<vector<int>> computers) {
for(int i =0;i<n;i++){
if(computers[i][i] && dfs(computers, i))
answer++;
}
return answer;
}
문제 풀이 2
#include <string>
#include <vector>
using namespace std;
void DFS(int point, vector<vector<int>>& computers, vector<bool>& visit, int n){
visit[point] = true;
for (int i = 0; i < n; i++) {
if (!visit[i] && computers[point][i]) DFS(i, computers, visit, n);
}
}
int solution(int n, vector<vector<int>> computers) {
int answer = 0;
vector<bool> visit(n, false);
for (int i = 0; i < n; i++) {
if (!visit[i]) {
answer++;
DFS(i, computers, visit, n);
}
}
return answer;
}
vector<bool> visit 을 이용해서 방문함을 표시하는 bool 함수 사용한다.
마찬가지로 1~n까지의 컴퓨터개수만큼 반복하는데 i번째 컴퓨터를 방문했는지 검사하고,
방문 못했다면 answer ++해주어 그 컴퓨터와 연결된 컴퓨터를 찾아가서 방문표시를 해주면서 돌아온다.
다시 main에서 그다음 컴퓨터 방문을 check할 때 안되어있는 컴퓨터만 검사한다.