[프로그래머스][Lv 2] 네트워크 (BFS)

코딩테스트 연습 - 네트워크 | 프로그래머스 (programmers.co.kr)

어제 bfs문제를 풀었어서 금방 푼 문제.

풀고나서 다른 풀이 봤더니 queue를 안쓰고 DFS 재귀를 돌리는 방법이 있었다. (BFS 재귀 x. dfs 재귀!!)

bfs든 dfs든 queue나 stack안쓰고 재귀 돌리는게 더 코드가 깔끔해보임. 생각하기 조금 더 까다로울 뿐!(+메모리 효율이 떨어짐)

 

내 코드

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

using namespace std;

bool  visited[200] = { false };
queue<int> q;

void bfs( vector<vector<int>> &computers,int& ans) {
    while(!q.empty()){
        int comNum = q.front();
        q.pop();

        //comNum 번째 computer와 연결된 모든 다른 com을 queue에 넣어줌
        for (int i = 0; i < computers.size(); i++) {
            if (computers[comNum][i] == 1 && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;

    //연결되지 않은 컴퓨터가 있는지 하나씩 확인.
    for (int i = 0; i < computers.size();i++) {
        if (!visited[i]) {
            answer++;
            q.push(i);
            bfs(computers, answer);
        }
    }

     return answer;
}