프로그래머스:네트워크

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

프로그래머스

 

풀이 1 : 인접리스트로 만들어서 풀기

#include <bits/stdc++.h>

using namespace std;
int visited[204];
vector<int> adj[204];
int dfs(int here){
    visited[here]=1;
    for(int there:adj[here]){
        if(visited[there]) continue;
        dfs(there);
    }

    return 1;
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    //인접리스트
    for(int i=0;i<computers.size();i++){
        for(int j=0;j<computers[i].size();j++){
            if(i==j) continue; //자기자신 제외
            if(computers[i][j]==1) adj[i].push_back(j);
        }
    }
    vector<int> comps = computers[0];
    for(int i=0;i<comps.size();i++){ //컴퓨터 개수만큼 반복
        if(visited[i]==0){
          answer += dfs(i);  

        } 
    }

    return answer;
}

 

다른 사람은 어떻게 풀었는지 확인해봤는데, 주어진 인접행렬을 이용하여 바로 푼 사람도 있었다.!!

 

#include <string>
#include <vector>

#define MAX 200

bool visitied[MAX];

using namespace std;

int DFS(vector<vector<int>> computers, vector<int> numbers, int n)
{
    visitied[n] = true;

    for (int i = 0; i < numbers.size(); ++i)
    {
        if (!visitied[i] && numbers[i] == 1) DFS(computers, computers[i], i);
    }

    return 0;
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;

    for (int i = 0; i < n; ++i)
    {
        if (!visitied[i])
        {
            DFS(computers, computers[i], i);
            answer++;
        }
    }

    return answer;
}

출처: https://school.programmers.co.kr/learn/courses/30/lessons/43162/solution_groups?language=cpp&type=all 

프로그래머스

 

위 로직대로 한번 풀어보았다.

풀이2: 주어진 배열로 풀기

#include <bits/stdc++.h>

using namespace std;
int visited[204];

void dfs(int here, vector<vector<int>>computers){
    visited[here]=1;
    for(int i=0;i<computers[here].size();i++){
        if(computers[here][i]==0) continue;
        if(visited[i]==0) dfs(i,computers);
    }
}

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