[프로그래머스] 네트워크 (Java)

프로그래머스

접근 방식

노드끼리 연결된 네트워크가 등장한다면 대체로 BFS와 DFS를 떠올리면 된다. 최단거리를 구해야 한다면 BFS를, 완전 탐색이 필요하다면 DFS를 사용해야하는데 이 문제에서는 모든 연결점을 탐색하여 네트워크의 개수를 파악해야하므로 DFS가 필요했다. 노드의 방문여부를 체크하고 종료조건을 삽입하기 위해 isVisited 배열을 활용했다.

로직 설명

solution 메서드

- 종료조건을 기록할 int[] isVisited 배열 선언

- computers배열에서 모든 노드의 연결정보를 순차적으로 탐색하며:

  방문 안 한 노드일 경우 방문하고 네트워크 증가(answer++)

- answer 반환

 

visit 메서드(DFS)

- 현재 노드를 방문하지 않았다면:

  1) 방문 표시

  2) computer배열에서 현재 노드(current)와 이어진 모든 다른 노드를 탐색하여 방문 

 

-> 하나의 노드에서 시작해서 이어진 모든 경로를 visit 메서드를 활용해 먼저 탐색하면서 방문표시를 한다. 그렇게 되면 그 다음 순번의 노드부터는 방문한 노드를 스킵하고, 새로운 네트워크인 경우(이전의 다른 노드들과 이어진 적 없는 경우)에만 네트워크 개수를 추가하게 된다. 예를 들어 5개의 노드가 있는데 이 노드들이 다 연결되어있다고 하면, 0번 컴퓨터(노드)를 visit으로 탐색하면서 모든 노드를 다 방문하게 된다. 그리고 하나의 네트워크가 추가된다. 이후의 노드들을 solution 메서드의 for문으로 탐색하더라도 이미 방문이 완료되어 스킵하므로 1을 반환하게 된다. 

작성 코드

class Solution {
    public int solution(int n, int[][] computers) {
        
        int[] isVisited = new int[computers.length];
        
        int answer = 0;
        
        for(int i = 0; i < computers.length; i++){
            if(isVisited[i] == 0){
                visit(i, computers, isVisited);
                answer++;
            }
        }
        
        return answer;
    } 
    
    public void visit(int current, int[][] computer, int[] isVisited){
        if(isVisited[current] == 0){
            
            isVisited[current] = 1;
        
            for(int i = 0; i < computer[current].length; i++){
                if(computer[current][i] == 1){
                    visit(i, computer, isVisited);
                }
            }  
        }
    }
}