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

●문제

 

●입출력

 

문제이해 : 문제를 이해하는데 꽤나걸렸다 이차원 배열 computer의 숫자가 의미하는건

[[1, 1, 0], [1, 1, 0] ,[0, 0, 1]]이 의미하는건 

//1번 컴퓨터는 자기자신, 2번연결 o / 3번연결 x [1, 1, 0]
//2번 컴퓨터는 자기자신, 1번연결 o / 3번연결 x [1, 1, 0]
//3번 컴퓨터는 자기자신, 1번연결 x / 2번연결 x [0, 0, 1] 을 의미한다

 

네트워크의 갯수는 독립적으로 [1,2] 는 네트워크 연결되었음으로 한개

[3] 은 서로 연결안되어있음으로 독립적으로 한개 이렇게 총 두개이다

 

문제풀이 : dfs로 서로 연결되어있거나 방문하지않았을때 dfs 재귀호출을 하였다

#include <string>
#include <vector>
#include <iostream>
using namespace std;

//만약 dfs로 연결되어있다면
//컴퓨터의 갯수 n / 2차원배열 computers / 네트워크 갯수 return

//1번 컴퓨터는 자기자신, 2번연결 o / 3번연결 x [1, 1, 0]
//2번 컴퓨터는 자기자신, 1번연결 o / 3번연결 x [1, 1, 0]
//3번 컴퓨터는 자기자신, 1번연결 x / 2번연결 x [0, 0, 1]
//network갯수는 [1,2] 서로연결 -> answer +1 / [3] 독립적 -> answer +1 답은 2
int answer = 0;
void DFS(int index, vector<vector<int>>& computers, vector<bool> &visited)
{
    visited[index] = true;
    for (int i = 0; i < computers.size(); i++)
    {
        //만약 연결되어있거나 방문하지않았으면 
        if (computers[index][i] == 1 && !visited[i])
        {
            //재귀호출
            DFS(i, computers, visited);
        }
    }
}
int solution(int n, vector<vector<int>> computers) 
{
    vector<bool>visited(n, false);
    for (int i = 0; i < n; i++)
    {
        //방문안했으면 체크
        if (!visited[i])
        {
            DFS(i, computers, visited);
            answer++;
        }
    }
    return answer;
}
int main(void)
{
    int n = 3;
    vector<vector<int>> computers = { {1, 1, 0}, {1, 1, 0}, {0, 0, 1} };
    int result = solution(n, computers);
    cout << result;
}

 

레벨 : 3

점수 : 1

 

-----

dfs 어렵네요.. 공부부족이 많이 느껴집니다