[프로그래머스 Lv3] : 네트워크

문제 링크

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

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

여러대의 컴퓨터가 연결되어 있을 때, 서로 정보를 교환할 수 있는 컴퓨터들의 그룹을 네트워크라고 한다.

네트워크의 총 개수를 세어보자.

 

  풀이

컴퓨터가 직접적으로 연결되어있지 않아도 간접적으로 정보를 교환할 수 있어도 같은 네트워크에 있는 것으로 간주한다.

이 문제는 백준에 있는 유기농배추 문제와 비슷한 문제인 듯하다.

 

참고 링크

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

한 지점에서 DFS로 탐색을 해서 더 이상 이동하지 못할 때 까지 탐색을 했을 때 이동 경로상에 있었던 노드들은 모두 같은 네트워크 안에 있는 것으로 생각할 수 있다.

이미 탐색된 지점은 중복방문을 방지하기 위해 bool 타입의 visited 배열을 이용해서 방문표시를 해주었다.

그리고 computers[i][j] == 1 이면 i와 j는 연결이 되어있다는 뜻이다.

(visited[j] && computer[i][j] == 1) 이면 재귀함수를 통해 j컴퓨터를 방문한다.

 

코드 작성

#include <string>
#include <vector>
using namespace std;
const int MAX_N = 200 + 5;
bool visited[MAX_N];
 
void dfs(int now, int n, vector<vector<int>> computers){
    visited[now] = true;
    for(int i = 0; i < n; i++){
        if(!visited[i] && computers[now][i])
            dfs(i, n, computers);
    }
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i = 0; i < n; i++){
        if(!visited[i]){
            dfs(i, n, computers);
            answer++;
        }
    }
    return answer;
}