[프로그래머스] (깊이/너비 우선 탐색) 네트워크

Computer를 탐색해나가며 나와 연결된 Computer를 찾아서 하나의 네트워크로 묶어야 한다.

 

 

 

 

1. 1번 컴퓨터를 시작으로 탐색을 시작한다. isConnect[0] = true 마킹

2. 1번 컴퓨터와 연결된 컴퓨터를 찾는다.(computers[?][0] == 1 인것)

3. 3번째 배열에서 computers[2][1] == 1 을 만족하므로 isConnect[2] = true 마킹

4. 다음 탐색을 시작한다.

 

 

 

 

 

 

 

 

 

5. 다시 3번 컴퓨터와 연결된 컴퓨터를 찾는다.(computers[?][2] == 1 인것)

6. 4번째 배열에서 computers[3][2] == 1 을 만족하므로 isConnect[3] = true 마킹

7. 다음 탐색을 시작한다.

8. 4번 컴퓨터와 연결된 컴퓨터를 찾는다.(comcomputers[?][3] == 1 인것)

9. 이미 마킹한 컴퓨터(isConnect[?] == true) 인 것을 제외하면 찾을 수 없으니 탐색을 종료한다.

10. 아직 연결되지 않은 컴퓨터(isConnect[?] == false) 부터 탐색을 시작한다.

 

 

 

 

모든 컴퓨터의 탐색을 마치면(isConnect 가 전부 true인 상태) 탐색을 종료하고 네트워크 수를 반환한다.

 

최종적으로 [1, 3, 4] 가 1개의 네트워크로 묶이고 [2] 는 단독 네트워크로 총 2개의 네트워크가 생성된다.

 

 

 

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

        for (int i = 0; i < computers.length; i++) {
            if(isConnect[i] == false) {
                answer++;
                findNetwork(computers, isConnect, i);
            }
        }
        return answer;
    }
    
    public void findNetwork(int[][] computers, boolean[] isConnect, int node) {
        for (int i = 0; i < computers.length; i++) {
            if(isConnect[i] == false && computers[node][i] == 1 ) {
                isConnect[i] = true;
                findNetwork(computers, isConnect, i);
            }
        }
    }
}

 

 

 

출처: 프로그래머스 코딩 테스트 연습, 
https://programmers.co.kr/learn/challenges