[프로그래머스/C++, C#] 네트워크

문제

---

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

프로그래머스

 

 

 

 

 

 

 

 

 

 

코드

---

1)BFS

 

- C++

#include <string>
#include <vector>
#include <queue>

using namespace std;

bool visited[200];

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i=0;i<computers.size();i++){
        if(!visited[i]){
            visited[i]=true;
            answer++;
            queue<int> q;
            q.push(i);
            while(!q.empty()){
                int temp = q.front();
                q.pop();
                for(int j=0;j<computers[temp].size();j++){
                    if(computers[temp][j]==1&&!visited[j]){
                        visited[j]=true;
                        q.push(j);
                    }
                }
            }
        }
    }
    return answer;
}

 

 

- C#

using System;
using System.Collections.Generic;

public class Solution {
    bool[] visited = new bool[200];
    public int solution(int n, int[,] computers) {
        int answer = 0;
        for(int i=0;i<n;i++){
            if(!visited[i]){
                answer++;
                visited[i]=true;
                Queue<int> q = new Queue<int>();
                q.Enqueue(i);
                while(q.Count>0){
                    int temp = q.Dequeue();
                    for(int j=0;j<n;j++){
                        if(computers[temp,j]==1&&!visited[j]){
                            visited[j]=true;
                            q.Enqueue(j);
                        }
                    }
                }
            }
        }
        return answer;
    }
}

 

 

 

2) DFS

 

- C++

#include <string>
#include <vector>

using namespace std;

bool visited[200];

void DFS(vector<vector<int>> com, int n, int temp){
    for(int i=0;i<n;i++){
        if(com[temp][i]==1&&!visited[i]){
            visited[i]=true;
            DFS(com, n, i);
        }
    }
}

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

 

 

 

- C#

using System;

public class Solution {
    bool[] visited = new bool[200];
    private void DFS(int n, int[,] com, int temp){
        for(int i=0;i<n;i++){
            if(com[temp, i]==1&&!visited[i]){
                visited[i]=true;
                DFS(n, com, i);
            }
        }
    }
    public int solution(int n, int[,] computers) {
        int answer = 0;
        for(int i=0;i<n;i++){
            if(!visited[i]){
                answer++;
                visited[i]=true;
                DFS(n, computers, i);
            }
        }
        return answer;
    }
}

 

 

 

풀이

---

그래프 탐색을 활용.

방문하지 않은 컴퓨터를 기점으로 네트워크 개수를 1 증가하고 탐색하여 컴퓨터와 네트워크로 연결되어 있는 모든 컴퓨터들을 방문.

다시 방문하지 않은 컴퓨터가 나올 때까지 돌다가 발견하면 위의 방식 실행을 반복.

 

 

다른 사람 코드

---

다른예시 1

#include <string>
#include <vector>
using namespace std;
vector<int> p;
int find(int u) { return u == p[u] ? u : (p[u] = find(p[u])); }
void merge(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return;
    p[u] = v;
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0, i, j;
    p.resize(n);
    vector<bool> vi(n, 0);
    for(i=0;i<n;i++) p[i] = i;
    for(i=0;i<n;i++) for(j=0;j<n;j++)
        if(computers[i][j]) merge(i,j);
    for(i=0;i<n;i++)
        if(!vi[find(i)]) {
            answer += 1;
            vi[find(i)] = 1;
        }
    return answer;
}

 

 

유니온 파인드를 사용한 예시.