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

 

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

코딩테스트 연습 - 네트워크

네트워크

문제

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

 

풀이

입출력 예시

 

풀이

DFS나 BFS를 활용할 수만 있다면 쉽게 풀리는 문제였다. DFS 또는 BFS를 마친 후 아직 방문하지 않은 정점이 있다면( = 다른 네트워크가 있다) DFS나 BFS를 또 진행해주면 된다.

 

DFS 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void DFS(int v, vector<bool> &visited, int com_size, vector<vector<int>> computers) {
    visited[v] = true;

    for (int w = 0; w < com_size; w++) {
        if (computers[v][w] != 0 && visited[w] == false) {
            DFS(w, visited, com_size, computers);
        }
    }
}

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

    DFS(0, visited, n, computers);
    answer++;

    vector<bool>::iterator iter = find(visited.begin(), visited.end(), false);
    while (iter != visited.end()) {
        DFS(iter - visited.begin(), visited, n, computers);
        answer++;
    
        iter = find(visited.begin(), visited.end(), false);
    }

    return answer;
}

 

BFS 풀이

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

using namespace std;

void BFS(int v, vector<bool> &visited, int com_size, vector<vector<int>> computers) {
    queue<int> visit_q;

    visited[v] = true;
    visit_q.push(v);

    while (!visit_q.empty()) {
        v = visit_q.front();
        visit_q.pop();

        for (int w = 0; w < com_size; w++) {
            if (computers[v][w] != 0 && visited[w] == false) {
                visited[w] = true;
                visit_q.push(w);
            }
        }
    }
}

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

    BFS(0, visited, n, computers);
    answer++;

    vector<bool>::iterator iter = find(visited.begin(), visited.end(), false);
    while (iter != visited.end()) {
        BFS(iter - visited.begin(), visited, n, computers);
        answer++;
    
        iter = find(visited.begin(), visited.end(), false);
    }

    return answer;
}