프로그래머스 - 네트워크 (dfs)

programmers.co.kr/learn/courses/30/lessons/43162#

코딩테스트 연습 - 네트워크

어려운 문제는 아니였는데 

 

  for (int i = target+1; i < n; i++) {
        if (computers[target][i] == 1 && target != i && visited[target][i] == 0) {
            visited[target][i] = visited[i][target] = 1;
            dfs(i, n, computers);
        }
    }

이렇게 해버려서 틀렸다. 

dfs들어갈 때 찾는 기준을 N보다는 크게 하면 모든선을 다 연결할 수 있다고 생각해버림 

[[1, 0, 1, 1, 0, 0], [0, 1, 0, 0, 1, 1], [1, 0, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1]]

이 반례가 있었다.... 이거로 해결!!

 

반례찾기가 너무 힘드네 ㅠㅠ 

 

#include <string>
#include <vector>

using namespace std;
int map[202];
int cnt;
int visited[201][201];
void dfs(int target,int n, vector<vector<int>> computers) {
    map[target] = cnt;
    for (int i = 0; i < n; i++) {
        if (computers[target][i] == 1 && target != i && visited[target][i] == 0) {
            visited[target][i] = visited[i][target] = 1;
            dfs(i, n, computers);
        }
    }
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    cnt = 0;
    for (int i = 0; i < n; i++) {
        if (map[i] == 0) {
            cnt++;
            dfs( i, n, computers);
        }
    }
    answer = cnt;
    return answer;
}