반갑습니다!

[프로그래머스] 네트워크 본문

알고리즘 문제 풀이

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

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

풀이

네트워크가 몇 개의 그룹으로 구성되어있는지 확인하는 문제이다. 방문 여부를 체크하는 배열을 만들고 DFS탐색을 하면 같은 네트워크에 속한 컴퓨터들은 재귀적으로 DFS 탐색을 하기 때문에 solution 함수에서 DFS를 총 몇 번 수행하는지를 세어주면 된다.

코드

#include <string>
#include <vector>

using namespace std;

void dfs(int n, vector<vector<int>>& computers, vector<bool>& visited, int idx){
    visited[idx] = true;

    for(int i=0; i<n; i++){
        if(!visited[i] && computers[idx][i])
            dfs(n, computers, visited, i);
    }
}

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

'알고리즘 문제 풀이' 카테고리의 다른 글

[백준] 14890 경사로  (0) 2020.05.08
[프로그래머스] 셔틀버스  (0) 2020.05.07
[프로그래머스] 타겟 넘버  (0) 2020.05.07
[SWEA] 2383 점심 식사시간  (0) 2020.05.07
[백준] 14889 스타트와 링크  (0) 2020.05.06