[프로그래머스] 네트워크 문제 (Java DFS 풀이)

안녕하세요.

오늘은 자바(Java)의 DFS를 이용한 프로그래머스 Lv.3 네트워크 문제를 풀어보겠습니다.

 

문제 설명

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

프로그래머스

입력값으로 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어집니다. 필요한 네트워크 개수를 return 하면 되는 문제입니다.

 

네트워크 개수는 컴퓨터끼리 연결되는 그룹의 개수 생각하시면 됩니다.

• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현
• computers[i][j]는 항상 1 (즉, 자기 자신과는 항상 연결되어 있음)

문제 예시도 살펴보겠습니다.

프로그래머스 문제 입출력 - 네트워크

• 첫 번째 예시 : computers 배열을 그림으로 나타내면 아래처럼 나타낼 수 있습니다. 1과 2가 연결되어 있고 3번이 혼자 있으므로 필요한 네트워크 개수는 2개입니다.

• 두 번째 예시 : computers 배열을 그림으로 나타내면 아래처럼 나타낼 수 있습니다. 1과 2가 연결되어 있고 2와 3이 연결되어 1과 3이 간접적으로 연결되어 정보를 교환할 수 있으므로, 1,2,3이 하나의 네트워크 상에 있다고 볼 수 있습니다. 그러므로 필요한 네트워크 개수는 1개입니다.

 

풀이 과정

• boolean 'check' 배열은 이미 네트워크를 거쳐갔는지, 즉 visited 했는지를 체크하는 용도로 쓰입니다.
• 컴퓨터의 개수 n만큼 도는 for문에서는 거쳐가지 않은 컴퓨터(!check[i])가 있으면 dfs 함수를 실행하고 이후 answer를 1만큼 증가시킵니다.
• 또한 dfs 함수에서는 시작하자마자 check[i] 를 true로 변경하여 방문했음을 알려주어야 합니다.

여기서 가장 중요한 문제는 '그룹화'입니다.

첫 번째 노드(i=0)부터 시작할 때, dfs 함수에서 첫 번째 노드가 어떠한 노드와 연결되어 있는지 (간접적, 직접적으로)를 모두 찾습니다(check[i]를 true로 바꿔서). 그러면 첫번째 노드를 기준으로 '그룹화'가 진행됩니다.

 

그러면 다음 for문으로 넘어가면(i=1), 이미 방문한 노드가 아닌 것(check[i]==true)을 찾아 dfs 함수를 실행시키고 answer를 증가시킵니다. 즉, 두 번째 노드부터 방문하지 않은 노드를 탐색하여, 방문하지 않은 노드가 k 노드라면, k노드를 기준으로 다시 '그룹화'를 진행하는 것입니다. 이후는 반복되겠습니다.

 

이렇게 되면 그룹 개수가 answer 변수에 저장되는 구조가 될 것입니다.

예시

• 위의 예시를 토대로 코드가 어떻게 흘러가는지 한번 구상해보시면 좋을 것 같습니다.
• 그룹이 3개, answer가 3이 됩니다.

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] check = new boolean[n];
        
        for(int i=0;i<n;i++){
            if(!check[i]){
                dfs(computers, i, check);
                answer++;
            }
        }
        
        return answer;
    }
    
    public void dfs(int[][] computers, int i, boolean[] check){
        check[i] = true;
        
        for(int j=0;j<computers.length;j++){
            if(i != j && computers[i][j] == 1 && !check[j]){
                dfs(computers, j, check);
            }
        }
    }
}

 

실행 결과

프로그래머스 문제 실행결과 - 네트워크

 

• 모든 테스트 결과를 통과하였습니다.

---

 

지금까지 자바(Java) DFS를 이용한 프로그래머스 '네트워크' 문제에 대해서 살펴보았습니다.

읽어주셔서, 감사합니다.