프로그래머스_네트워크(C++)

 

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

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

[문제 풀이]

DFS를 이용하여 문제를 풀었습니다.

 

이 문제는 컴퓨터를 연결하는 간선의 정보가 입력으로 들어왔을 때 서로 직간접적으로 연결된 그래프의 그룹의 개수 찾는 문제입니다. A와 직접 연결된 정점들과 정점들의 연결된 컴퓨터를 탐색하는 방법으로 문제를 해결했습니다.

문제의 로직은 반복문을 돌면서 방문하지 않은 컴퓨터라면 DFS에 인덱스값을 전달하여 연결된 컴퓨터들을 확인하는 식으로 구현하였습니다. 

[C++]

#include <string>
#include <vector>

using namespace std;



bool visit[201];

void DFS(int n, vector<vector<int>> computers, int idx){
    
    for(int j = 0; j < n; j++){
        
        if(idx == j)
            continue;
        
        if(computers[idx][j] == 1 && !visit[j]){
            visit[j] = true;
            DFS(n, computers, j);
        }
    }
    
}

int solution(int n, vector<vector<int>> computers) {

    int answer = 0;
    
    for(int i = 0; i < n; i++){
        
        if(!visit[i]){
            visit[i] = true;
            DFS(n, computers, i);
            answer++;
        }
        
    }
    
    
    return answer;
}

[JAVA]

import java.util.*;

class Solution {
    int[][] network;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        network = new int[n][n];
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(computers[i][j] == 1)
                    network[i][j] = 1;
            }
        }
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(network[i][j] == 1){
                    network[i][j] = 0;
                    DFS(i);
                    answer++;
                }    
            }
        }
        
        return answer;
    }
    
    void DFS(int idx){
        
        for(int j = 0; j < network[idx].length; j++){
            if(network[idx][j] == 1){
                network[idx][j] = 0;
                DFS(j);
            }
        }
    }
    
}