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

▶문제설명

코딩테스트 연습 > DFS/BFS > 네트워크

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

▶ 설계

---

DFS로 해결이 가능한 문제이다.

2차원 벡터 매개변수인 computers는 인접행렬로 정점들 사이의 간선 여부를 나타낸다.

문제에서 연결 요소를 네트워크라고 표현했을 뿐, 그래프의 연결 요소의 개수를 세서 리턴하는 문제라고 생각하면 된다.

네트워크가 몇 개인지를 구하는 함수의 시그니처를 정의해보자.

void findNetworkNum(int n, int nowComputer, const vector<vector<int>>& computers, vector<bool>& visited){
 
}

매개변수명	의미
n	컴퓨터의 개수
nowComputer	현재 컴퓨터
computers	컴퓨터들 사이의 연결 여부
visited	이미 방문한 컴퓨터를 체크하기 위한 1차원 배열

아직 방문하지 않았고 연결되어 있어서 이동 가능한 컴퓨터로 재귀호출을 통해 옮겨가며 방문을 체크하도록 구현하자.

▶ 구현

---

우선 findNetworkNum()에 필요한 인자를 전달해주고 컴파일 가능한 상태로 만들어주자.

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

이제 findNetworkNum()를 구현해보자.

void findNetworkNum(int n, int nowComputer, const vector<vector<int>>& computers, vector<bool>& visited){
    visited[nowComputer] = true;
    
    for(int linkedComputer=0; linkedComputer<n ;linkedComputer++){
        if(visited[linkedComputer] == false && computers[nowComputer][linkedComputer]){
            findNetworkNum(n, linkedComputer, computers, visited);
        }
    }
}

line 2 : 현재 컴퓨터를 방문했음을 체크한다.

line 4~8 : 현재 컴퓨터와 연결된 컴퓨터들 중 아직 방문하지 않은 컴퓨터를 찾아서 재귀호출한다.

solution 함수의 5번째 라인에서 findNetworNum(n, 0, computers, visited)을 호출했으므로 0번 컴퓨터에서 하나의 연결요소를 찾게 된다.

하지만 우리는 모든 연결요소를 찾아야 하므로 solution 함수 내부를 조금 수정해야한다.

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> visited(n, false);
    for(int computer=0; computer<n ;computer++){
        if(visited[computer] == false){
            findNetworkNum(n, computer, computers, visited);
            answer++;
        }
    }
    return answer;
}

이런 식으로 0번 컴퓨터부터 n-1번 컴퓨터까지를 확인하면서 아직 방문하지 않은 경우에만 findNetworkNum을 호출해주면 모든 네트워크의 개수를 구할 수 있게 된다.

▶ 결과

---

▶Solution

---

[소스코드 보기]