프로그래머스 네트워크

작성일 | In |

Problem : 네트워크

유형 : DFS

문제 해석

  • 네트워크가 몇개 있는지 찾아라.

문제 재해석

  • 연결 되어있는 그래프의 개수가 네트워크의 개수이다.

해결 전략

  • DFS를 통해서 각 정점에서 연결된 정점을 전부 순회한다.

설계, 구현

  • 시작점이 이미 방문한 곳인 경우, 이미 네트워크를 이룬 노드이므로 넘어간다.
  • 시작점이 새로운 곳이라면, 새로운 네트워크가 존재 하는것이다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;


vector<int> node[202];
bool visit[202];

void dfs(int com) {
    for (auto& nxt_com : node[com]) {
        if (visit[nxt_com]) continue;
        visit[nxt_com] = true;
        dfs(nxt_com);
    }
}

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

    for (int cur_computer = 0; cur_computer < n; ++cur_computer) {
        for (int other_computer = 0; other_computer < n; ++other_computer) {
            if (computers[cur_computer][other_computer]) {
                node[cur_computer].push_back(other_computer);
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (visit[i]) continue;
        visit[i] = true;
        answer++;
        dfs(i);
    }
    return answer;
}

int main() {

    int n = 3;
    vector<vector<int>> vec{ {1, 1, 0}, { 1, 1, 0 }, { 0, 0, 1 }};
    cout << solution(n, vec);
    return 0;
}

피드백

  • 다른 level3 에 비해서 너무 쉽다.