고득점 Kit [DFS/BFS] - 네트워크

문제

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

풀이

// function solution(n, computers) {
//     // n 가로길이, 세로길이
//     let graph = computers 
    
    
//     let answer = 0;
    
//     function dfs(graph, n, x, y) {
//         if (x<= -1 || x>=n || y<=-1 || y >= n) {
//             return false
//         } 
        
//         if (graph[x][y] == 1) {
//             graph[x][y] = -1;
            
//             dfs(graph, n, x-1, y)
//             dfs(graph, n, x+1, y)
//             dfs(graph, n, x, y-1)
//             dfs(graph, n, x, y+1)
            
//             return true
//         }
        
//         return false
//     }
    
    
    
    
//     for (let i=0; i<n; i++) {
//         for (let j=0; j<n; j++) {
//             if (dfs(graph, n, i, j)) answer++
//         }
//     }
    
//     return answer
// }

원래 풀었떤 코드이다. 입출력은 모두 통과가 뜨는데 테스트케이스에서 모든 케이스를 통과 하지 않았다.

function solution(n, computers) {
    
    // 각 컴퓨터는 0부터 n-1인 정수로 표현 : 즉, 컴퓨터의 이름은 각 인덱스
    
    let answer = 0;
    // 맨 처음 0번 컴퓨터부터 시작하기 위해 처음 visited값을 false로
    const visited = [false];
    
    function dfs(i) {
        // 0번 컴퓨터 반복처리
        visited[i] = true;
        
        // 0번 컴퓨터의 모든 인덱스를 뒤지다가
        for (let j = 0; j < n; j++) {
            // [i][j]가 1이라는 것은 다른 컴퓨터와 연결 되어 있다는 것
            // j랑 연결이 되어있고 j를 방문하지 않았다면 j도 검사
            // 0번 컴퓨터는 1번과 연결 돼있어서 0, 1번 컴퓨터를 "한번에" 검사 -> dfs(j)를 수행하며 visited[j]값이 true
            if (computers[i][j] === 1 && !visited[j]) {
                dfs(j); 
            }
        }
    }
    
    for (let i = 0; i < n; i++) {
        if(!visited[i]) { // ☆ 최종 : visited[i]가 false일 때지만, 0할 때 1까지 true바뀌었으니.
            // 0번 컴퓨터부터 시작, (computer[i][i]는 항상1이므로 무조건 각 네트워크니까)
            // visited가 true일 때마다 answer의 값을 증가시킴        
            dfs(i);
            answer++;
        }
    }

   return answer;
}