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

🌽 문제

🥔 풀이

dfs 연습용 난이도 정도 되는 것 같다.
푸는 방법이 생각나서 다행이다.

처음에 냅다 bfs로 풀려다가 틀었다.
0이랑 이어진 컴퓨터만 확인 가능하므로 당연히 안되는 코드다.

int cnt = n;

q.push(0);
used[0] = true;
.
.
.
if (!used[next] && com[now][next])
	cnt--;
.
.
.
return cnt;

for (int i = 0; i < n; i++) q.push(i)
뭐 이런 창의적으로 그지같은 풀이로도 도전해봤으나 명백한 dfs 문제였다.

🥬 코드

#include <vector>
using namespace std;

vector<bool> used;

void dfs(vector<vector<int>> com, int now) {
    for (int next = 0; next < com.size(); ++next) {
        if (!com[now][next]) continue;
        if (used[next]) continue;
        used[next] = true;
        dfs(com, next);
    }
}

int solution(int n, vector<vector<int>> computers) {
    used.resize(n, false);
    
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        used[i] = true;
        dfs(computers, i);
        cnt++;
    }
    return cnt;
}

🥜 채점