[Lv3] 네트워크

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

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

 

양방향 그래프일때 행렬은 대각선 기준 대칭이니까, 반을 기준으로 왼쪽 아래 행렬은 탐색할 필요가 없다고 생각했다. 이 경우, computers가 아래와 같이 주어지면, 결과가 2가 아닌 4가 나온다.

 

let arr = [

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

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

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

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

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

];

---

function solution(n, computers) {
    let visited = new Set();
    let col = computers.length;
    let row = computers[0].length;
    var answer = 0;

    function search(x, y, depth) {
        for (let i = y; i < col; i++) {
            if (depth === 0 && !visited.has(i)) {
                visited.add(i);
                answer++;
            } else if (depth === 0 && visited.has(i)) continue;

            for (let j = x; j < row; j++) {
                if (visited.has(j)) {
                    continue;
                } else if (computers[i][j] === 1) {
                    visited.add(j);
                    search(0, j, depth + 1);
                }
            }

            if (depth !== 0) return;
        }
    }

    search(0, 0, 0);

    return answer;
}