Level 3. 네트워크

Level 3. 네트워크

 

 

i와 j 컴퓨터가 연결된 경우, i와 j의 연결을 끊고 i와 j부터 DFS를 수행해 연결된 컴퓨터들을 처리한다.

 

#include <iostream>
#include <vector>

using namespace std;

void rDFS(int i, int j, int n, vector<vector<int>>& computers)
{
    computers[i][j] = computers[j][i] = 0;

    for (int k = 0; k < n; ++k)
        if (computers[i][k])
            rDFS(i, k, n, computers);

    for (int k = 0; k < n; ++k)
        if (computers[j][k])
            rDFS(j, k, n, computers);
}

int solution(int n, vector<vector<int>> computers)
{
    int answer = 0;

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= i; ++j)
        {
            if (computers[i][j])
            {
                rDFS(i, j, n, computers);
                ++answer;
            }
        }
    }
            
    return answer;
}

 

내 풀이는 이중 for문을 사용해 다소 비효율적이지만, 이 풀이는 computers[i][j] == computers[j][i]인 점을 이용해 n 크기의 방문 여부를 별도로 저장해 for문 1개로 해결했다.

 

#include <iostream>
#include <vector>

using namespace std;

void rDFS(int i, vector<vector<int>>& computers, vector<bool>& visited)
{
    visited[i] = true;

    for (int j = 0; j < computers.size(); ++j)
        if (!visited[j] && computers[i][j])
            rDFS(j, computers, visited);
}

int solution(int n, vector<vector<int>> computers)
{
    int answer = 0;
    vector<bool> visited(n, false);

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