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

서론

문제를 보고 연결된 네트워크 따라 탐색시키면 되겠다 생각하고 코드를 완성한 후 분류를 봤더니 DFS/BFS문제다. 그리고 다시 내 코드를 봤더니 BFS였다.

BFS는 생각하지도 않았는데 자연스럽게 BFS로 풀이된게 뿌듯하다. 조금은 체화된것같다.

풀이

DFS/BFS문제

answer를 1 증가시키면서 1번 노드에 방문하면 방문표시를 한다. 그리고 방문한 노드와 연결된 노드가 있고 아직 방문을 안했으면 방문하고 방문표시를 한다. 더이상 연결된 노드가 없을때까지 탐색하면 하나의 네트워크를 만들 수 있다.

그리고 위의 과정 전체를 아직 방문하지 않은 노드가 남아있을 때까지 반복한다.

구현

// c++

#include <string>
#include <vector>
#include <queue>

using namespace std;

int node[201];

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    queue<int>q;
    
    for(int i=0, size = computers.size(); i<size; i++){
        if(node[i] == 1) continue;
        q.push(i);
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(int j=0; j<size;j ++){
                if(computers[cur][j] == 1 && node[j] == 0) {
                    node[j] = 1;
                    q.push(j);
                }
            }
        }
        answer++;
    }
    
    return answer;
}