C++ / 프로그래머스 / 네트워크 / 문제 풀이

---

네트워크

---

 

<문제>

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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개의 네트워크가 있습니다.

 

 

<풀이>

각 컴퓨터에 연결 된 네트워크 개수를 구하는 문제이다.

computer[i][i]는 항상 1이므로 하나도 연결되지 않은 컴퓨터 3개는 {1,0,0}, {0,1,0}, {0,0,1}이다.

예제 1로 주어진 배열은 {1,1,0}, {1,1,0}, {0,0,1} 이므로 1번과 2번만 연결되어 있음을 알 수 있다. 그림과 같이 1번과 2번 컴퓨터는 같은 네트워크 상에 있고 3번 컴퓨터는 혼자 분리되어 있다.

따라서 네트워크의 개수는 2개이다.

 

예제 2는 {1,1,0}, {1,1,1}, {0,1,1} 이므로 1번과 2번이 연결, 2번과 3번이 연결되어 있다. 그림과 같이 3개의 컴퓨터가 하나로 연결되어 있다.

따라서 네트워크의 개수는 1개이다.

 

예제를 통해 알 수 있는 것은 컴퓨터가 연결되어 있다면 네트워크 개수에 영향을 주지 않는다는 것이다.

따라서 n개의 컴퓨터를 하나씩 확인해서 연결된 컴퓨터, 즉 1인 것만 지우면 네트워크 개수를 셀 수 있다.

computer[i][i]를 기준으로 잡고, 연결된 경우에는 computer[i][i]를 0으로 바꿔줌으로써 네트워크 개수를 셀 때 제외시킨다.

 

다양한 풀이 방법이 있지만

그래프의 모든 정점을 방문해야하기 때문에 깊이 우선 탐색법(DFS)인 재귀함수로 풀어보도록 하겠다.

참고) DFS란? https://devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

 

 

#include <vector>

using namespace std; // 2차원 벡터를 사용하기 위해 클래스 std 호출

bool countNetwork(vector<vector<int>>& computers, int n){ // &로 참조형 변수선언
    if(!computers[n][n]){ // false, 즉 0인 경우
        return false; //한번 확인한 노드는 제외시킴
    }
    computers[n][n] = 0; // 연결되어있다면 0으로 처리(삭제)해줘서 네트워크 개수에 영향을 주지않음
    for(int i = 0; i < computers.size(); i++){
        if(computers[n][i]){ // true, 즉 1인 경우
            countNetwork(computers, i); // 재귀
        }
    }
    return true;
}

int solution(int n, vector<vector<int>>computers){
    int answer = 0;
    for(int i = 0; i < n; i++){
        if(computers[i][i] && countNetwork(computers, i)){ // computer[i][i]가 기준
            answer++;
        }
    }
    return answer;
}

예제 1의 경우 

i=0 일때 문제에서 주어진 {1,1,0}, {1,1,0}, {0,0,1} 에서 함수를 거치면

computer[0][0] =0, computer[1][1] = 0 로 바뀌므로 

{0,1,0}, {1,0,0}, {0,0,1} 가 되고 answer가 1이 된다.

i=1 일때는 2번이 삭제된 컴퓨터이므로 넘어간다.

i=2 일때 3번 컴퓨터는 0으로 바뀌게 되고 answer가 2가 된다.

 

예제 2의 경우 

i=0 일때 1,2,3 컴퓨터는 0으로 바뀌게 되고 answer가 1이 된다.

i=1 일때 2번 컴퓨터는 삭제된 컴퓨터이므로 넘어간다.

i=2 일때 3번 컴퓨터는 삭제된 컴퓨터이므로 넘어간다.

 

 

<실행 결과>

테스트 1
입력값 〉	3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
기댓값 〉	2
실행 결과 〉	테스트를 통과하였습니다.

테스트 2
입력값 〉	3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
기댓값 〉	1
실행 결과 〉	테스트를 통과하였습니다.

테스트 3
입력값 〉	4, [[1, 1, 0, 0], [1, 1, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1]]
기댓값 〉	1
실행 결과 〉	테스트를 통과하였습니다.

테스트 4
입력값 〉	4, [[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1]]
기댓값 〉	2
실행 결과 〉	테스트를 통과하였습니다.

테스트 결과

4개 중 4개 성공

 

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43162

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

 

참고 https://mungto.tistory.com/52