[Lv.3] 네트워크 with cpp

# 생각

연결된 그래프의 개수를 구하는 문제이다

그래프의 연결된 노드들을 따라 탐색하다가 연결이 끊기면 네트워크 하나가 끝난 것이므로

+1로 네트워크 개수를 구할 수 있다

 

컴퓨터별로 탐색여부를 체크하는 방문배열을 선언해주고

i번째 컴퓨터가 아직 검색하지 않은 컴퓨터일때 탐색을 시작해주면 된다

 

재귀가 끝나면 그래프 한개가 연결된 상태이므로 answer++를 해주면 된다

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;

int vis[222];
// dfs를 이용한 풀이
void dfs(vector<vector<int>>& v, int depth)
{
    vis[depth] = 1;
    for (int i = 0; i < v[depth].size(); i++)
    {   // depth번째와 연결된 컴퓨터들 탐색
        if (!vis[i] and v[depth][i] == 1)
        {   // 아직 방문하지 않았으면서, 다른 컴퓨터와 연결되 있다면
            dfs(v, i);
        }
    }
}
// bfs를 이용한 풀이
void bfs(vector<vector<int>>& v, int st)
{
	vis[st] = 1;
	queue<int> q;
	q.push(st);

	while (!q.empty())
	{
		int x = q.front(); q.pop();
		for (int i = 0; i < v.size(); i++)
		{
			if (vis[i] == 1 or v[x][i] == 0) continue;
			else
			{
				vis[i] = true;
				q.push(i);
			}
		}
	}
}

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

    for (int i = 0; i < n; i++)
    {   // 아직 검사하지 않은 컴퓨터일때
        if (!vis[i])
        {
            //dfs(computers, i);
            //bfs(computers, i);
            answer++;   // 재귀가 끝나면 연결된 그래프 하나
        }
    }

    return answer;
}

 

---

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges