문제 푼 날짜 : 2021-08-18

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43162

접근 및 풀이

컴퓨터(노드)와 컴퓨터(노드) 사이의 연결관계를 알기 위해서 DFS를 떠올렸다.
그런데 DFS를 적용할 때, 익숙한 인접행렬 좌표를 이용한 것이 아닌, 노드에 DFS를 적용하기 위해 computers 배열을 인접 리스트로 변형해주었다.
그 다음, 각 컴퓨터에서 방문할 수 있는(연결되어 있는) 모든 컴퓨터를 방문하고 더이상 방문할 컴퓨터가 없을 때 네트워크 갯수를 +1해주어 네트워크의 갯수를 구해주었다.
문제를 풀고 나서 다른 분들의 풀이를 보니 굳이 인접 리스트로 변형해주지 않아도 된다는 것을 알게되었다...

코드

#include <string>
#include <vector>

using namespace std;

vector<int> v[201];
bool visited[201] = { false };

void dfs(int vertex) {
    visited[vertex] = true;
    for (int i = 0; i < v[vertex].size(); i++) {
        if (visited[v[vertex][i]] == true) {
            continue;
        }
        dfs(v[vertex][i]);
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                continue;
            }
            if (computers[i][j] == 1) {
                v[i + 1].push_back(j + 1);
                v[j + 1].push_back(i + 1);
            }
        }
    }
        
    for (int i = 1; i <= n; i++) {
        if (visited[i] == true) {
            continue;
        } else {
            dfs(i);
            answer++;
        }
    }
    return answer;
}

결과

피드백

아직 멀었다. 더 열심히 하자.