프로그래머스 : 네트워크(C++, Lv.3, DFS)

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

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

풀이 참고 블로그

풀다가 도저히 생각나지 않아서 여러 블로그 글을 봤는데 그나마 이 블로그 글이 내가 기존에 알던 내용을 응용해서 풀어주었다.

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

먼저 필자는 문자에서 주어진 2차원 벡터를 n x n 행렬로 생각해 행을 j로, 열을 i로 두고 생각해 문제를 풀었다.

 

소스코드

#include <string>
#include <vector>

using namespace std;

//해당 행의 방문 여부 체크, 1: 방문 0:미방문
bool visited[200];

//DFS 수행
void dfs(vector<vector<int>> &computers, int j) {
    //해당 행 방문 처리
    visited[j] = true;
    for(int i=0; i<computers.size(); i++) {
        //computer[k][k] 는 무조건 1이므로 넘기기 
        if(i==j) continue;
        
        //아직 방문하지 않았고 해당 행렬값이 1인 경우 dfs 방문
        if(!visited[i] && computers[j][i]) {
            dfs(computers, i);
        }
    }
    
}


int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    //0~n 탐색해 이미 방문했는지 확인  행렬로 표현해 i는 가로행, j는 세로행으로 생각
    for(int j = 0; j< n; j++) {
        //이미 방문한 노드인 경우
        if(visited[j]) continue;
        
        //방문하지 않은 경우 dfs 수행
        answer++;
        dfs(computers, j);
    }
    return answer;
}