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

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

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

 

1. 서론

 

DFS/BFS 문제 좀 풀려고 풀어본 문제. level 3이라는데 3치곤 좀 쉬운 듯(물론 난 어려웠음)

 

2. 문제 풀이

 

n개의 컴퓨터가 있는데 이들이 연결되어 있는지, 아닌지의 여부가 주어진다. 연결되어 있으면 하나의 네트워크라고 한다. 그렇다면 몇 개의 네트워크로 이루어져 있는가를 구하는 문제이다.

 

https://coding-log.tistory.com/138?category=954740 

[C++] 프로그래머스 전력망을 둘로 나누기

 

전에 풀었던 이 문제와 상당히 유사하다. (그래서 풀 때 약간 참조했다 ㅎㅎ)

 

나의 풀이법)

나는 일단 주어진 배열을 토대로 네트워크를 실제로 만들었다. 그러니까 연결되어 있는지 아닌지 여부를 받아서 실제로 배열들을 연결했다.

(보통의 DFS/BFS 기초 문제처럼 ㅎ)

그리고 그 상태에서 DFS를 활용해 n번의 컴퓨터부터 시작했을 때 그 경로들을 따로 배열에 저장했다. 그리고 그 배열들을 정렬해서 그 내용이 같으면 같은 네트워크이므로 다른 내용이 발견되면 카운트를 해서 몇 개의 네트워크가 있는지 계산해줬다.

(진짜 비효율적인 걸 알지만 사고력이 딸리는 관계로 이딴식으로 풀 수밖에 없었음)

그리고 맞기는 했지만 이렇게 푸는게 아니라는 걸 알기 때문에 다른 사람은 어떻게 풀었나 풀이를 찾아봤다.

 

정석 풀이법)

https://dokylee.tistory.com/79

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

이 블로그에 따르면 주어진 배열을 따라 dfs를 돌다 보면 그 함수를 호출한 수가 네트워크의 개수란다...

어렴풋이 감이 잡히지만 딱 떠올릴 자신은 없다. 다음에 유사문제 나오면 활용해봐야지... 이렇게 배우는 거겠지...? ㅎ

 

3. 코드설명

 

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

using namespace std;
int k = 0;
int visit[201];
vector<int> v[201];
vector<int> x;

void dfs(int start)
{
    if (visit[start] == true) return;
    visit[start] = true;
    x.push_back(start);

    for (int i = 0; i < v[start].size(); i++)
    {
        int x = v[start][i];
        dfs(x);
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0, i, j;
    vector<vector<int>> a;
    vector<int> t;

    for (i = 0; i < computers.size(); i++)
    {
        for (j = 0; j < computers[i].size(); j++)
        {
            if (i != j && computers[i][j] == 1)
            {
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }            
    }

    for (i = 0; i < n; i++)
    {
        dfs(i);
        a.push_back(x);
        memset(visit, 0, sizeof(visit));
        memset(&x, 0, sizeof(x));
    }

    for(i = 0; i < a.size(); i++)
        sort(a[i].begin(), a[i].end());

    sort(a.begin(), a.end());

    for (i = 0; i < a.size(); i++)
    {
        for(j = 0; j < a[i].size(); j++)
            cout << a[i][j] << " ";
        cout << endl;
    }

    t = a[0];
    answer = 1;
    for (i = 1; i < a.size(); i++)
    {
        if (t != a[i])
        {
            answer++;
            t = a[i];
        }
    }

    return answer;
}

 

위에서 말한 그대로다.

배열로 연결해주고... 그걸 dfs 돌려서 방문 순서 적어주고... 그 배열을 정렬해서 앞과 뒤의 값이 달라지면 cnt 해주는... 그런 비효율적인 코드 ㅎㅎ

(절대로 이렇게 풀지 말기를)