와이유스토리

[DFS 단순 반복] 프로그래머스 네트워크 C++ 본문

코딩테스트/그래프|트리

[DFS 단순 반복] 프로그래머스 네트워크 C++

유(YOO) 2022. 1. 20. 21:35

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

#include <string>
#include <vector>

using namespace std;

bool check[201];

void dfs(int n, vector<vector<int>> computers, int idx){
    for(int i=0; i<n; i++) { // i=idx 아님(작을 수도O)
        if(check[i]) continue;
        if(computers[idx][i] == 1) {
            check[i] = true;
            dfs(n, computers, i);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i=0; i<n; i++) {
        if (check[i] != true) {
            check[i] = true;
            dfs(n, computers, i);
            answer++;
        }
    }
    
    return answer;
}
#include <string>
#include <vector>

using namespace std;

bool check[201];

void dfs(int n, vector<vector<int>> computers, int idx){
    check[idx] = true;
    
    for(int i=0; i<n; i++) // i=idx 아님(작을 수도O)
    {
        if((computers[idx][i] == 1) && (check[i]!=true)) // 한 번 더 체크 필요
        {
            dfs(n, computers, i);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i=0; i<n; i++) {
        if (check[i] != true) {
            dfs(n, computers, i);
            answer++;
        }
    }
    
    return answer;
}

※ Union-Find 풀이

https://whyou-story.tistory.com/66?category=912481 

 

[Union-Find] 프로그래머스 네트워크

#include #include #include #include using namespace std; int parent[201]; int find(int x) { if (x == parent[x]) { return x; } return parent[x] = find(parent[x]); } void unions(int x, int y) { x = fi..

whyou-story.tistory.com

 

'코딩테스트 > 그래프|트리' 카테고리의 다른 글

[DFS 순열] 프로그래머스 여행 경로 C++  (0) 2022.01.20
[DFS 순열] 프로그래머스 단어 변환 C++  (0) 2022.01.20
[DFS 단순] 프로그래머스 타겟 넘버 C++  (0) 2022.01.20
[DFS, BFS] 백준 12100 2048(Easy) C++  (0) 2022.01.06
[DFS 조합 반복] 프로그래머스 메뉴 리뉴얼 C++  (0) 2022.01.01
'코딩테스트/그래프|트리' Related Articles more
Comments