[프로그래머스] Lv.3 네트워크 - C++

potatoj11n·2024년 1월 20일

프로그래머스

목록 보기

15/25

🌱 문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다
각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
computer[i][i]는 항상 1입니다.

입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

입출력 예 설명

예제 #1

아래와 같이 2개의 네트워크가 있습니다.

예제 #2

아래와 같이 1개의 네트워크가 있습니다.

풀이

❣️ 문제 요약:

컴퓨터(노드) 간의 연결이 있다면 연결된 노드끼리는 하나의 네트워크를 공유하는 것으로 해서 연결된 네트워크의 총 개수를 구한다. 서로 인접하지 않아도 연결된 공통 노드가 있다면 하나의 네트워크다.

🤔 생각해야 할 점

두 개의 정점이 연결되어 있을 때 한 노드에 연결된 다른 정점이 있다면 인접하지 않은 두 노드도 연결된다.
연결이 된 노드들은 하나의 네트워크로 생각하고 연결되지 않은 노드는 하나의 개별 네트워크이다.
모든 노드가 연결되었을 때 네트워크 갯수는 하나다.

→ dfs 알고리즘을 이용해서 먼저 1번 컴퓨터와 연결된 컴퓨터를 dfs 로 탐색해 나가고 1번과 연결된 컴퓨터 중 1번과 연결되지 않았지만 1번과 연결된 컴퓨터와 연결된 컴퓨터를 또 한번의 dfs로 찾는다. 탐색하지 않은 컴퓨터가 없을 때 까지 진행한다.

✅ 1. 아직 탐색안한 i 번째 컴퓨터를 dfs(i) 로 탐색

i 와 연결된 컴퓨터 j 가 아직 탐색하지 않은 컴퓨터이면 dfs(j) 로 탐색
아직 탐색하지 않은 컴퓨터가 없을 때 까지 탐색

이게 끝나면 하나의 네트워크를 찾은 것이다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool checked[201];

void DFS(int x, int n, vector<vector<int>>& computers) {

    checked[x] = true; // true->방문한 노드
    for (int i = 0; i < n; i++) {
        if (!checked[i] && computers[i][x] == 1)
            // 방문안한 노드이고 x랑 연결이 있으면 
            DFS(i, n, computers); // 방문         
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for (int i = 0; i < n; i++) {
        if (!checked[i]) {
            DFS(i, n, computers);
            answer++;
        }
    }
    return answer;
}

코드 설명

✅ bool checked[201] : 이미 연결된 컴퓨터인지 확인하는 함수 checked

✅ 방문하지 않았던 노드를 방문해서 이어진 노드들까지 탐색하는 함수 DFS( 하나의 네트워크를 찾는 함수)

void DFS(int x, int n, vector<vector<int>>& computers) {
    checked[x] = true; // true->방문한 노드
    for (int i = 0; i < n; i++) {
        if (!checked[i] && computers[i][x] == 1)
            // 방문안한 노드이고 x랑 연결이 있으면 
            DFS(i, n, computers); // 방문         
    }
}

void DFS(int x, int n, vector<vector<int>>& computers) : x 는 현재노드 n 은 컴퓨터 수 computers 벡터에 수정사항을 반영하려면 참조를 해줘야한다. 참조를 하지 않으면 배열의 변경사항이 반영되지 않는다.
checked[x] = true; : 현재 노드에 방문함을 표시하기 위해 true로 입력
if (!checked[i] && computers[i][x] == 1) :인덱스 i 가 아직 방문하지 않은 노드이고 현재 노드 x와 연결된 노드이면 재귀함수를 사용해 다시 DFS함수를 실행한다.

✅ 인덱스를 키워가며 현재 컴퓨터가 연결되어 있는지 확인하고 DFS 함수를 호출해 네트워크 수를 세는 solution 함수

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for (int i = 0; i < n; i++) {
        if (!checked[i]) {//방문하지 않은 컴퓨터이면
            DFS(i, n, computers);//DFS 함수 호출
            answer++;//네트워크 수 증가
        }
    }
    return answer;
}

초기 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool checked[201];
void DFS(int x, int n,vector<vector<int>> computers){
    checked(x) = true;
    for( int i =0;i < n ;i++){
         if(checked[i]==false && computer[i][j]==1)
             DFS(x,n,computers);         
    }
        
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i =0; i <n ; i++){
        if(checked[i] ==false)
            DFS(i,n,computers);
            answer++;
    }
        
    return answer;
}

✅ 틀린 부분

void DFS(int x, int n,vector<vector<int>> computers)
→ void DFS(int x, int n,vector<vector<int>>& computers)
: computers 벡터에 수정사항을 반영하려면 참조를 해줘야한다. 참조를 하지 않으면 배열의 변경사항이 반영되지 않는데 이 부분을 생각하지 못했다.

그리고 DFS 함수의 매개변수를 잘못 넣어서 호출했었다. for문 내에서 i 인덱스를 돌리면서 i 인덱스가 포함되는지 확인해야하는데 x를 넣었다.

potatoj11n

이전 포스트

[프로그래머스] Lv.1 문자열 내 p와 y의 개수 - c++

다음 포스트

[프로그래머스] Lv.3 네트워크 - C++