[프로그래머스 43162] Lv.3 네트워크

문제 Link

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

프로그래머스

문제풀이 Key Point

1	1	0
1	1	0
0	0	1

• { 0, 0 } 에서 시작한다.
• 따라서 0번째 컴퓨터는 이미 하나의 네트워크와 연결되어 있다라고 확인 할 수 있다.
• 0행의 열 전체를 검사하면서 연결된 컴퓨터가 있는지 확인한다.
• 0행 1열의 컴퓨터가 즉, 1번째 컴퓨터가 0번 컴퓨터와 연결되어 있다.
• 1행의 열 전체를 검사하면서 아직 연결이 확인되지 않은 컴퓨터들만 검사한다.
• 0행과 1행의 검사가 종료되고 마지막 2행의 열 전체를 확인한다.
• 하나로 연결된 네트워크 확인이 종료되면 카운트 +1을 해준다.
• 2행 2열인 즉, 2번 컴퓨터는 아직 확인 되지 않았으므로 네트워크 한 개를 갖고 있는 것을 확인 할 수 있다.
• 이렇게 과정을 그리다보면 DFS를 이용해야 한다는 것을 알 수 있다.

아래에 똑같이 표현해보기

👇👇👇

• for (int i = 0; i < 행의 갯수; i++)
• visited[0] = true;   👉   index번째 컴퓨터의 네트워크 연결을 확인
• for(int i = 0; i < 열의 갯수; i++)
• visited[1] = true; 
• answer++;   👉   하나로 연결된 네트워크 카운트
• visited[2] = true;

그림으로 표현해보기

👇👇👇

Java 풀이

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            if(!isVisited(visited, i)) {
                findNetworkConnect(computers, visited, i);
                answer++;
            }
        }
        return answer;
    }
    
    private void findNetworkConnect(int[][] computers, boolean[] visited, int x) {
        visited[x] = true;
        
        for (int i = 0; i < computers.length; i++) {
            if (validateNextConnect(visited, computers, x, i)) {
                findNetworkConnect(computers, visited, i);
            }
        }
    }
    
    private boolean validateNextConnect(boolean[] visited, int[][] computers, int x, int y) {
        return isNetworkConnect(computers, x, y) && !isVisited(visited, y);
    }
    
    private boolean isNetworkConnect(int[][] computers, int x, int y) {
        return computers[x][y] == 1;
    }
    
    private boolean isVisited(boolean[] visited, int index) {
        return visited[index];
    }
}