[programmers] 네트워크 - Java

네트워크

문제 설명

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.

• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.

• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.

• computer[i][i]는 항상 1입니다.

입출력 예

입출력 예 설명

처음 작성한 코드

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = n;
        for(int i=0; i<computers.length-1; i++){
            for(int j=i+1; j<computers[i].length; j++){
                if(computers[i][j]==1)
                    answer--;
                if(answer==1)
                    return answer;
            }
        }
        return answer;
    }
}

수정한 코드

class Solution {
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n];
        int networks = 0;

        for (int i = 0; i < n; i++) {
            System.out.println(visited[i]);
            if (!visited[i]) {
                dfs(computers, visited, i);
                networks++;
            }
            
        }
        return networks;
    }

    private void dfs(int[][] computers, boolean[] visited, int node) {
        visited[node] = true;
        for (int neighbor = 0; neighbor < computers.length; neighbor++) {
            if (computers[node][neighbor] == 1 && !visited[neighbor]) {
                dfs(computers, visited, neighbor);
            }
        }
    }
}

핵심 키워드

• 처음 작성한 코드는 두 컴퓨터 간에 연결이 발견될 때마다 네트워크 개수를 감소시켜 문제를 해결하려고 했다.
• 그러나 이 경우 간접 연결을 고려하지 않고 직접 연결 수만 계산하므로 네트워크 수를 정확하게 계산하지 못했다.

• 이를 해결하기 위해 DFS를 적용해서 코드를 작성했다.
• DFS 순회 중에 방문한 컴퓨터를 추적하는 데 사용할 boolean 배열을 선언해서, 만약 방문하지 않았다면 dfs()를 실행한다.
• dfs() 를 실행하면 방문한 컴퓨터를 표시하고, 해당 컴퓨터와 다른 컴퓨터의 연결 여부를 순회한다.
• 해당 컴퓨터가 다른 컴퓨터와 연결되어 있고, 연결된 컴퓨터를 방문하지 않았을 경우 dfs() 메소드를 재귀 호출한다.
• 해당 컴퓨터의 방문이 완료되면 네트워크 수를 증가시킨다.

결론!