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

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

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

 

 

문제 풀이

n은 컴퓨터의 개수이고 최대 200개이다.

따라서 방문 여부 체크를 할 수 있는 visited 배열은 200번째 인덱스까지 선언해준다.

0번 컴퓨터부터 n번 컴퓨터까지 DFS를 거쳐 연결된 컴퓨터를 체크한다.

 

DFS 함수 내부에는 다시 0부터 n까지 해당 노드와 연결되어 있는 노드들에 대해서 DFS를 거치는데, 문제의 조건 중에서 1번과 2번과 연결되어 있고 2번과 3번이 연결되어 있을 때, 1번과 3번은 연결되어 있다고 했기 때문에 같은 네트워크에 포함되어야 한다.

 

1번 테스트 케이스로 예를 들면, 아래와 같이 연결 정보가 주어진다.

 

[1, 1, 0]

[1, 1, 0]

[0, 0, 1]

 

첫 번째 컴퓨터에서 DFS를 거치며 2번째 컴퓨터와 연결되어 있음을 알고 visited 배열에 체크한 뒤 DFS가 끝나면 하나의 네트워크를 순회하였으므로 answer를 ++해준다. 다음으로, 두 번째 컴퓨터는 이미 방문하였으므로 DFS를 진행하지 않고 넘어간다. 마지막으로 3번째 컴퓨터를 DFS하면 하나의 네트워크가 추가되므로 다시 answer를 ++해주어 answer = 2를 리턴한다.

 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

bool visited[201] = { false, };

void DFS(vector<vector<int>> computers, int n, int x){
    visited[x] = true;
    
    for(int i=0; i<n; i++){
        if(!visited[i] && computers[x][i]){
            DFS(computers, n, i);
        }
    }
}


int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i=0; i<n; i++){
        if(!visited[i]) {
            DFS(computers, n, i);
            answer++;
        }
    }
    
    return answer;
}