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

문제

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

프로그래머스

 

풀이

💡 문제 접근

• 한 컴퓨터와 연결된 다음 컴퓨터를 탐색하고, 그 다음 컴퓨터와 연결된 컴퓨터를 계속해서 탐색해 나간다.
• 탐색 중 연결이 끊기면 하나의 네트워크가 완성된 것 = 네트워크 + 1

💡 DFS, 재귀함수

1. 1번 컴퓨터와 연결되어 있는 컴퓨터를 탐색하기 위해 dfs 함수를 호출한다.
2. 1번 컴퓨터가 2번 컴퓨터와 연결되어 있는 것을 발견한다.
3. 2번 컴퓨터와 연결되어 있는 컴퓨터를 탐색하기 위해 dfs 함수를 호출한다.
   이때, 2번 컴퓨터와 1번 컴퓨터가 연결되어 있는 것을 알 수 있지만, 1번째 컴퓨터는 이미 탐색한 컴퓨터이다.

---

이 과정을 아래와 같이 정리할 수 있다.

1. 방문하지 않은 i번째 컴퓨터를 탐색하기 위해 dfs 함수를 호출한다.
2. i번째 컴퓨터와 연결되어있는 컴퓨터를 탐색하기 위해 dfs 함수를 호출한다.
   이때, 탐색하는 컴퓨터는 방문하지 않은 컴퓨터이다.
3. dfs 함수가 종료되면 더이상 연결된 컴퓨터가 없는 것이므로 네트워크를 추가한다.

코드

#include <iostream>
#include <vector>

using namespace std;

vector<bool> isVisited;

void dfs(int cur, int n, vector<vector<int>> computers) {
    isVisited[cur] = true;  // 방문 표기

    for (int i = 0; i < n; i++) {
        // 방문하지 않은 컴퓨터이고, 현재 컴퓨터와 연결되어 있다면
        if (!isVisited[i] && computers[cur][i]) {
            dfs(i, n, computers);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    isVisited.assign(n, false);

    for (int i = 0; i < n; i++) { // 컴퓨터 방문
        if (!isVisited[i]) { // 아직 방문하지 않은 컴퓨터
            dfs(i, n, computers);
            answer++;
        }
    }

    return answer;
}