[프로그래머스] 네트워크 c++ java (dfs) Level3

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

풀이

연결되어 있는 네트워크의 개수를 찾는 문제이다.

하나의 네트워크를 끝까지 하나씩 탐색하므로 dfs를 활용하자!

---

1. main

처음 컴퓨터 개수만큼 반복하며 방문하지 않은 경우 dfs를 실행하며 정답 카운터를 1 증가시킨다.

2. dfs

방문한 노드를 true처리한 후, for문을 돌아 연결되어 있는 경우(computers[idx][i]) && 방문하지 않은 경우(!visit[i]) dfs를 재귀 호출한다.

---

코드 (C++)

#include <string>
#include <vector>

using namespace std;

void dfs(int idx, vector<vector<int>> &computers, vector<bool> &visit, int n){
    visit[idx] = true;
    for(int i = 0; i < n; i++){
        if(computers[idx][i] && !visit[i])
            dfs(i, computers, visit, n);
    }
}

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

코드 (Java)

import java.util.*;

class Solution {

    public void dfs(int idx, int[][] computers, boolean visited[], int n){
        visited[idx] = true;        
        for(int i = 0; i < n; i++){
            if(computers[idx][i] == 1 && !visited[i]){
                dfs(i, computers, visited, n);
            }
        }
    }

    public int solution(int n, int[][] computers) {
        int answer = 0;

        boolean visited[] = new boolean[n];

        for(int i = 0; i < n; i++){
            if(!visited[i]) {
                answer++;
                dfs(i, computers, visited, n);
            }
        }

        return answer;
    }
}