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

 

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

 

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

프로그래머스

---

 

 

해결전략

 

너비우선탐색 BFS 

유니온 앤 파인드 Union & Find

 

아래 풀이는 BFS

---

 

 

처음 시도한 코드

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int answer; // 네트워크 개수
int cnt; // 연결된 컴퓨터 수
vector<vector<int>> ch; // 방문 여부를 체크

void BFS(int start, int n, vector<vector<int>> com) // BFS를 수행하여 연결된 컴퓨터들을 방문
{
    queue<int> Q;
    Q.push(start);

    while (!Q.empty())
    {
        int curr = Q.front();
        Q.pop();
        ch[curr][curr] = 1;  // 현재 컴퓨터 방문 표시

        for (int i = 0; i < n; i++)
        {
            if (ch[curr][i] == 0 && com[curr][i] == 1) { // 연결된 컴퓨터 찾기
                ch[curr][i] = 1; // 방문 표시
                ch[i][curr] = 1; // 방문 표시
                Q.push(i);       // 다음 컴퓨터를 큐에 추가
                cnt++;           // 연결된 컴퓨터 수 증가
                //cout << "curr = " << curr << ", next = " << i << "\n";
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    ch.resize(n, vector<int>(n));

    for (int i = 0; i < n; i++)
    {
        if (ch[i][i] == 0) { // 방문하지 않은 컴퓨터 찾기
            BFS(i, n, computers);
        }
    }

    answer = n - cnt; // 네트워크 수 계산

    return answer;
}

int main() {
    vector<vector<int>> computers = {
        {1, 1, 0},
        {1, 1, 0},
        {0, 0, 1}
    };
    cout << solution(3, computers) << "\n; // 올바른 결과값: 2, 출력되는 결과값: 1
    return 0;
}

 

 

실수한 부분

• answer = n - cnt; 로 네트워크의 수를 계산하려고 했다. 
• cnt는 전체 컴퓨터 수가 아니라 BFS가 수행될 때마다 증가하는 연결된 컴퓨터의 수를 나타낸다.
• cnt가 정확하게 네트워크의 수를 반영하지 않기 때문에 문제가 된다.

---

 

 

정답코드 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int answer; // 네트워크 개수
vector<int> visited; // 방문 여부를 체크

void BFS(int start, int n, vector<vector<int>>& computers) // BFS를 수행하여 연결된 컴퓨터들을 방문
{
	queue<int> Q;
    Q.push(start);

    while (!Q.empty())
    {
        int curr = Q.front();
        Q.pop();
        ch[curr][curr] = 1; // 현재 컴퓨터 방문 표시

        for (int i = 0; i < n; i++)
        {
            if (ch[curr][i] == 0 && com[curr][i] == 1) { // 연결된 컴퓨터 찾기
                ch[curr][i] = 1; // 방문 표시
                ch[i][curr] = 1; // 방문 표시 
                Q.push(i);       // 다음 컴퓨터를 큐에 추가
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    visited.resize(n, 0);

    for (int i = 0; i < n; i++)
    {
        if (ch[i][i] == 0) { // 방문하지 않은 컴퓨터 찾기
            BFS(i, n, computers); // BFS 수행
            answer++; // 새로운 네트워크 발견 시 증가
        }
    }

    return answer;
}

 

 

각각의 BFS 연산을 할 때 마다 네트워크가 증가한다.

 

 

 

 

좀 더 간략화한 버젼

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int answer;
vector<int> visited;

void BFS(int start, int n, vector<vector<int>>& computers)
{
    queue<int> Q;
    Q.push(start);
    visited[start] = 1; // 현재 컴퓨터 방문 표시

    while (!Q.empty())
    {
        int curr = Q.front();
        Q.pop();

        for (int i = 0; i < n; i++)
        {
            if (!visited[i] && computers[curr][i] == 1) { // 연결된 컴퓨터 찾기
                visited[i] = 1; // 방문 표시
                Q.push(i);      // 다음 컴퓨터를 큐에 추가
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    visited.resize(n);

    for (int i = 0; i < n; i++)
    {
        if (false == visited[i]) { // 방문하지 않은 컴퓨터 찾기
            BFS(i, n, computers);
            answer++; // 새로운 네트워크 발견 시 증가
        }
    }

    return answer;
}

---