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

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

 

메모

- 주어진 모든 컴퓨터들은 computers[i][i]의 값이 1임

   -> 이걸 이용해서 방문한 컴퓨터에 대해서는 computers[i][i]의 값을 0으로 바꾸어 방문 표시하기

- dfs로 컴퓨터 방문해서 연결되어 있는 j 컴퓨터들(computers[i][j]의 값이 1인 컴퓨터들)에 대해서 dfs 수행

- dfs 내에 있는 computers[i][i]==0이면 return하는 조건문은 dfs가 중첩되어 수행되는 경우에 필요함

 

맞힌 코드

#include <bits/stdc++.h>

using namespace std;

void dfs(int i, vector<vector<int>> &computers){
    if (computers[i][i]==0)
        return;
    
    computers[i][i] = 0;
    for (int j=0; j<computers.size(); j++){
         if (computers[i][j]==1)
             dfs(j, computers);
    }
}

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

 

참고)

https://sayho98.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4C43162-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC

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