[프로그래머스 네트워크] c++ (풀이,코드,dfs)

문제 링크

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

프로그래머스

 

문제

 

코드, 풀이

level3라고 해서 꼭 어려운건 아닌거 같다는 생각이 드는 문제였습니다. level1이 더 까다로울때도 있고.. 신기하네요.

 

이 문제는 dfs로 풀었습니다.

 

dfs에서의 가장 핵심은 방문을 하였나? 안하였나가 가장 중요한 문제로 level3이지만 아마 dfs의 가장 기초적인 문제가 아니었나 싶습니다.

 

순서는 이렇게 짜봤습니다.

1. 방문을 하지 않았다면 0부터 computers.size() - 1 까지 dfs를 시작합니다.

    for(int i = 0; i < computers.size();i++){

        if(visited[i] ==0)

            dfs(i,computers);

    }

2. dfs안에서 시작하는 순간 방문을 처리하고 만약 연결된 반복문을 찾아 만약 방문하지 않았고 연결이 되었다면

dfs를 다시 돌립니다.

    visited[i] = 1;

->방문 여부 체크

 

    for(int idx = 0; idx < computers.size();idx++){

        if(visited[idx] == 0 && computers[i][idx] == 1){

            if(i!= idx)

                answer --;

            dfs(idx,computers);

        }

    }

-> 방문x 연결o -> dfs 하면서 answer--;

 

answer를 따로 coumputer.size()로 하여 처음에 모두 연결되지 않았다는 전제하에

연결이 된것을 확인할때마다 --를 진행하였습니다.

 

 

전체 코드

/*

네트워크

i -> j 연결 ->computer[i][j],computer[j][i]=1 로 연결x -> 0

computer[i][i]는 항상 1

dfs로 풀면 될듯?

*/

#include <string>

#include <vector>

#include <iostream>

using namespace std;

int visited[200]={0,};

int answer = 0;

void dfs(int i,vector<vector<int>> computers);

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

    answer = computers.size();

    for(int i = 0; i < computers.size();i++){

        if(visited[i] ==0)

            dfs(i,computers);

    }

    return answer;

}

void dfs(int i, vector<vector<int>> computers){

    visited[i] = 1;

    for(int idx = 0; idx < computers.size();idx++){

        if(visited[idx] == 0 && computers[i][idx] == 1){

            if(i!= idx)

                answer --;

            dfs(idx,computers);

        }

    }

}