[programmers] 네트워크 (Java)

[네트워크]

[코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 네트워크]

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

프로그래머스

 

 

[접근 방식]

이 문제는 접근 방식에 많은 우여곡절이 있었다.

1. 크루스칼 알고리즘을 응용하여 해결하는 방법 (실패!)

1-1) 해당 노드가 소속된 트리의 루트 노드를 기록하는 배열을 만든다.

1-2) 서로 독립적인 트리 2개를 병합한다. (Tree B 가 Tree A 에게 병합된다.) 

1-3) 병합된 트리에 소속된 노드 (Tree A 의 노드) 들의 루트 노드를 Tree B의 루트노드로 갱신한다.

 

이와 같은 방식으로 '루트 노드를 기록하는 배열' 을 중복 제거 하려고 했다.

(※ 배열 크기 == 독립된 Tree 의 개수 == 네트워크 개수)

 

//https://school.programmers.co.kr/learn/courses/30/lessons/43162
//코딩테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS) - 네트워크

import java.util.Arrays;

class Solution {
    public int solution(int n, int[][] computers) {

        // 각 노드가 속해 있는 트리의 루트 노드
        int[] rootArr = new int[n];
        for (int i = 0; i < n; i++) {
            rootArr[i] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (computers[i][j] == 1) {
                    if (find(rootArr, i) != find(rootArr, j)) {
                        unite(rootArr, i, j);
                    }
                }
            }
        }
        
        //배열 중복 제거
        int[] arr = Arrays.stream(rootArr).distinct().toArray();

        return arr.length;
    }

    private int find(int[] rootArr, int x) {
        if (rootArr[x] == x) {
            return x;
        }

        return find(rootArr, rootArr[x]);
    }

    private void unite(int[] rootArr, int x, int y) {
        int a = find(rootArr, x);
        int b = find(rootArr, y);
        rootArr[b] = a;
    }
}

 

프로그래머스에 별도로 테스트 케이스를 확인 할 수 있는 기능이 있는것이 아니라 잘 모르겠지만,
테스트에 실패하여서, 어쩔 수 없이 다른 방법을 사용하고자 한다.

2. DFS 를 활용하는 방법

DFS 를 통해 탐색이 완료된다면, 하나의 트리가 모두 탐색이 완료한 것이므로, 네트워크 1개 가 형성된 것이다.

 

[Java 코드]

//https://school.programmers.co.kr/learn/courses/30/lessons/43162
//코딩테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS) - 네트워크


class Solution {
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n];  // 방문 여부를 체크할 배열
        int answer = 0;  // 네트워크의 수

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {  // 아직 방문하지 않은 컴퓨터라면
                dfs(i, computers, visited);  // DFS를 수행하여 연결된 모든 컴퓨터를 방문
                answer++;  // 하나의 네트워크가 형성되었으므로 개수를 증가
            }
        }

        return answer;
    }

    // 깊이 우선 탐색 메소드
    private void dfs(int node, int[][] computers, boolean[] visited) {
        visited[node] = true;  // 현재 노드를 방문 처리

        for (int i = 0; i < computers.length; i++) {
            if (computers[node][i] == 1 && !visited[i]) {  // 연결되어 있고 아직 방문하지 않은 노드라면
                dfs(i, computers, visited);  // 재귀적으로 DFS를 수행
            }
        }
    }
}

 

[Rewind]

1. 어려웠던 점

- 크루스칼 알고리즘에 매몰되어 다른 방법을 생각해 내지 못한 것이 한스럽다.

 

2. 알게된 점

- 크루스칼 알고리즘은 단순히 '최소 신장 트리' 를 구할때만 사용하자.

- DFS 에 작동 개념을 더 확실히 알게되었다.

 

3. 개선방안

- 트리에 많은 약점이 있는 것 같다. 관련 문제를 더 많이 풀어야 한다.