네트워크

문제 설명
 
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
 
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
 
제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

 
입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 
입출력 예 설명
 
예제 #1
아래와 같이 2개의 네트워크가 있습니다.

 
 
예제 #2
아래와 같이 1개의 네트워크가 있습니다.

 
사용 언어 - Java

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {    
    
    private static int [][] array;
    
    public int solution(int n, int[][] computers) {
        
        array = computers;        
        boolean history[] = new boolean[n];
        
        int answer = 0;
        
        for(int i=0; i<n; i++){             
            if(!history[i]){
                bfs(history,i);   
                answer++;
            }            
        }            
        
        return answer;
    }
    
    private static void bfs(boolean history[], int cursor) {
        
        PriorityQueue<Integer> que = new PriorityQueue<>();

        /* offer()
           - 해당 큐 맨 뒤에 값 삽입
           - 값 추가 성공 시 true 반환
           - 값 추가 실패 시 false 반환 
        */
        
        que.offer(cursor);
        history[cursor] = true;
                
        /*
        poll()
           - 큐 맨 앞에 있는 값 반환 후 삭제
           - 큐가 비어있을 경우 null 반환
        */
        
        while(!que.isEmpty()){              
                 
            int index = que.poll();    
 
            for(int i=1; i < array.length; i++) { //해당 값의 행에 해당하는 데이터를 가져옵니다
                if(array[index][i] == 1 && history[i] == false) {    
                    que.offer(i);
                    history[i] = true;	
                }             
            }   
            
        }
        
    }

}

 
 
 

코딩테스트 후기
 
1) 프로그래머스 Level3.

 
2) 깊이우선탐색(DFS, Depth-First Search)와 너비우선탐색(BFS, Breadth-First Search)에 관한 문제이다. 면접 시험에서 `미로찾기`라는 이름으로 비슷한 테스트를 보았다. 어려웠다. 그래서 DFS, BFS를 알아보기로 했다. 바로 프로그래머스에서 해당 방식을 사용한 문제를 찾아서 풀었다. 쉽지 않았다. 구글링으로 DFS, BFS에 관한 코드를 읽었다. 직접적으로 답을 찾아서 본 것은 아니다.
 
3) 위의 코드는 너비우선탐색(BFS)로 문제를 풀었다.
 
4) 너비우선방식이란, 두 노드 사이의 최단 경로나 임의의 경로를 찾고 싶을 때 선택하는 방법이다. 자료구조 큐(Queue)를 사용하고 선입선출(FIFO,First In First Out)로 진행된다.
 
5) 위의 문제 2차원 배열로 들어오는 computers = ex) => [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 가 뜻하는 바를 파악해보았다.
해당 computers을 표로 만들어 보면 아래와 같다.

	A	B	C
A	1	1	0
B	1	1	0
C	0	0	1

 
각각의 컴퓨터가 연결되어 있으면 1, 연결되어있지 않으면 0으로 표기된다. 

 
  A, B, C는 항상 자기 자신과 연결되어 있는 상태이기 때문에  언제나 1을 갖는다.  A 컴퓨터를 먼저 보면 [1, 1, 0]으로 자기 자신과 B와 연결되어 있다. B 컴퓨터 또한 [1, 1, 0]으로 A와 자기 자신이 연결 상태이다. C 컴퓨터를 보면 [0, 0, 1] 로 오직 자기 자신만 연결된 상태이고 A, B와는 연결되어 있지 않은 상태이다. 이를 그림으로 표현한게 '예제 #1' 이다.
 
6) 코딩 작성 후, 테스트 케이스에 등록된 값에는 모두 정답이었다. 그러나 제출 후 채점하기에서는 정답률이 20% 밖에 되지 않아서 원인을 파악했다.  

//수정 전 
bfs(history,0);


//수정 후
int answer = 0;

for(int i=0; i<n; i++){             
    if(!history[i]){
        bfs(history,i);   
        answer++;
    }            
}

 수정 전에는 bfs함수를 0에서만 시작한다. 그 결과, A와는 연결되진 않지만  A가 아닌 다른 컴퓨터와 연결되어 네트워크를 이루는 컴퓨터를 파악할 수 없는 구조이다. 이를 반복문을 사용하여 각각의 컴퓨터의 연결 상태를 탐색할 수 있게 바꾸었다.
 
7) 마지막으로 네트워크 개수 출력에 대해서도 큰 고민이 있었다. 연결되어있는 컴퓨터는 파악했지만 네트워크 개수로 표기하는 방법이란 무엇인가. 고민 끝에 답지에서 살짝 힌트를 엿보기로 결정했다. 방법은 bfs(history,i); 함수가 끝나면서 answer을 1씩 증가시키는 방식으로 카운트를 하는 것이었다.
 
ex_ 테스트1의 입력값이 들어왔을 경우,

테스트 1
입력값 〉	3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
기댓값 〉	2
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	history : [true, false, false] index :0 index :1 i : 0 history : [true, true, true] index :2 i : 2

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {    
    
    private static int [][] array;
    
    public int solution(int n, int[][] computers) {
        
        array = computers;           
        
     	boolean history[] = new boolean[n];
        // 1. => [false, false, false]로 시작.
        
        int answer = 0;
        
        
                
        for(int i=0; i<n; i++){
        
            // 2. history[0]은 false이므로 bfs(history,i) 함수 실행.
            // 13. history = [true, true, false]로 변경 history[2]이 false이므로 반복문실행
            
            if(!history[i]){
                bfs(history,i);   
                
                // 12. answer = 1;
                // 19. answer = 2;
                answer++;
            }            
        }             
        
        
        return answer;
    }
    
    private static void bfs(boolean history[], int cursor) {
        
        PriorityQueue<Integer> que = new PriorityQueue<>();
        
        //3.큐(Queue)에 0삽입
        //14.큐(Queue)에 2삽입
        que.offer(cursor);
        
        //4.history[0] = true로 변경 => 탐색 완료 표시  [true,false,false]  
        //15.history[2] = true로 변경 => 탐색 완료 표시 [true,true,true]      
        history[cursor] = true;
               
               
        /* 5. que 구조 ===>  |0| | | | | |
              que가 비어있지 않으니 아래 while문 실행 */
        // 10. que구조 ===> |1| | | | | != empty
        // 16. que구조 ===> |2| | | | | != empty
        
        while(!que.isEmpty()){

            // 6. que안에 들어있는 0이 index에 들어가고 삭제
            // 11. que안에 들어있는 1이 index에 들어가고 삭제
            // 17. que안에 들어있는 2이 index에 들어가고 삭제
            int index = que.poll();    
 
            for(int i=1; i < array.length; i++) {
            
            	/* 7.
                     array = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
                	    => array[0][1] == 1                     
                     history = [true, false, false]
                        => history[1] == false;
                        
                     아래 조건문과 일치하여 실행
                */
                
                
                /* 11.
                    array[1][1] == 1 && history[1] == true ==> if문 실행X
                    array[1][2] == 0 && history[1] == true ===> if문 실행X
                    que구조 ===> | | | | | | == empty -> 함수 종료
                */
                
                /* 18.
                    array[2][1] == 0 && history[0] == true ==> if문 실행X
                    array[2][2] == 1 && history[2] == true ==> if문 실행X
                    que구조 ===> | | | | | | == empty -> 함수 종료
                */
                
                if(array[index][i] == 1 && history[i] == false) {  
                
                    que.offer(i);                    
                    // 8. que구조 ===> |1| | | | |
                    
                    history[i] = true;
                    // 9. [true, true, false]로 변경                    
                }             
            }   
            
        }
        
    }

}