[C++/PGS] Lv.3 : 네트워크 (DFS/BFS)

깊이/너비 우선 탐색(DFS/BFS) : 네트워크

문제 출처 - 프로그래머스 코딩테스트 고득점 Kit

 

문제 설명

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

---

 

늘 그랬듯이 삽질 열심히 했다

입력 형식이 matrix라서 bfs로 풀면 되겠구나~하면서 풀다가

코드가 너무 길어져서 때려치고

dfs로 풀었습니다.

bfs / dfs 둘 다 풀이가 가능하던데.. dfs 코드가 훨씬 짧고 간단함

 

일반적으로 최단거리 구하는 문제는 bfs가 편하고

다른건 대부분 dfs가 편한듯.

 

1. matrix에 속지 말고, visited는 1차원 배열로 선언한다. 그냥 방문한 노드만 체크하면 된다구
2. 현재 노드에 방문한 적 없으면 dfs 실행
3. 모든 노드 중에서 방문한 적 없고 && 현재 노드와 연결되어 있다면 탐색 계속 실행!

 

 

 

나의 풀이

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int visited[202] = {0,};

void dfs(int n, vector<vector<int>> computers,int current){
    visited[current] = 1;
    for(int i=0; i<n; ++i){
        if(visited[i]==0 && computers[current][i]==1){
            dfs(n,computers,i);
        }
    }
}

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