알고리즘) 프로그래머스 DFS/BFS, 네트워크

프로그래머스 고득점 Kit - DFS/BFS

네트워크

 

문제 설명

 

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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개의 네트워크가 있습니다.

풀이

(2020.04.21)

 

ArrayList를 이용해서 네트워크를 연결해준다음, 확인을 통해 갱신하면서 만들어진 네트워크들을 다시 한 번 ArrayList에 담았다. 이 크기를 리턴해주면서 네트워크의 갯수를 구해주었다. 간단한 문제라고 생각하고 접근했다가, 생각보다 까다로와서 시간이 조금 걸렸다. 코드에 주석이 있어서 이해하는데 어렵지는 않겠지만 주석이 없는 두 메소드를 간략하게 설명하고 싶다.

 첫째, 처음 초기화를 해주는 inItNetWork를 통해 전체 네트워크를 담을 ArrayList를 만들어 준다. 이 때, 첫 네트워크에 0을 넣어주고 return했는데, 자기 자신은 네트워크에 포함이 되기 때문에 넣어줬다. 코드의 로직을 따라가다보면 쉽게 이해될 것이다.

 둘째, serachNum 메소드이다. 해당 컴퓨터가 포함된 네트워크를 찾아, 그 네트워크의 index를 리턴해주는 메소드이다. 해당 컴퓨터가 네트워크에 등록되어 있지 않다면, -1을 리턴해주어 새로운 네트워크를 만들 수 있게 해줬다.

 

문제에 대한 이해력이랑 코드를 설계하는 능력이 아직도 많이 부족하다.. 조금 더 분발하자!!

 

---

(2020.06.05)

 

find-union, dfs 두 방법에 대해 각각 코드를 짜보았다.

처음 짤 때, ArrayList로 네트워크를 List로 구현해서 풀었었는데, 아마 시간이 오래걸렸을 것이다.

find-union과 dfs로 푸는데는 그리 오랜 시간이 걸리지 않았다.

이 문제에서는 dfs의 효율이 가장 좋은 것 같다.

 

코드 1

 

package programmers;

import java.util.ArrayList;

public class KitDBFSNetwork {
    private static int solution(int n, int[][] computers) {
        ArrayList<ArrayList<Integer>> networks = inItNetwork();

        for(int i=0; i<n; i++) {
            int idx = searchNum(networks,i);    // i번째 컴퓨터가 포함된 네트워크 탐색
            ArrayList<Integer> origin;
            if(idx ==-1) {  // 없으면 네트워크 생성
                origin = new ArrayList<>();
                origin.add(i);
            } else {    // 있으면 네트워크 가져오기
                origin = networks.get(idx);
                networks.remove(idx);   // 해당 네트워크는 목록에서 제거
            }

            for(int j=0; j<computers[i].length; j++) {
                if(i !=j && computers[i][j] ==1) {  // i번째 컴퓨터에 연결된 j(target) 컴퓨터
                    int targetIdx = searchNum(networks, j); // target이 다른 네트워크랑 연결됐는지 확인
                    if(targetIdx != -1) {   // target이 연결된 네트워크가 존재하면
                        ArrayList<Integer> network = networks.get(targetIdx);   // 받아와서
                        for(int num : origin) {
                            if(!network.contains(num)) {
                                network.add(num);   // 네트워크를 합쳐주고
                            }
                        }
                        origin = network;   // origin 교체
                        networks.remove(targetIdx); // network 목록에서 제거
                    } else {
                        origin.add(j);  // i에 j 연결
                    }
                }
            }
                networks.add(origin);   // 네트워크 리스트에 완성된 네트워크 추가
        }

        return networks.size();
    }

    private static ArrayList<ArrayList<Integer>> inItNetwork() {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> tmp = new ArrayList<>();
        tmp.add(0);
        result.add(tmp);

        return result;
    }

    private static int searchNum(ArrayList<ArrayList<Integer>> networks, int num) {
        int result =-1;

        for(int idx=0; idx<networks.size(); idx++) {
            if(networks.get(idx).contains(num)) {
                result = idx;
                break;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int n = 3;
        int[][] computers = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
//        int n = 3;
//        int[][] computers = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
        System.out.println(solution(n, computers));
    }
}

 

코드 2

 

class Solution {    // dfs
    int[] visit;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visit = new int[n];
        for(int i=0; i<computers.length; i++) {
            if(visit[i] ==0) {
                dfs(i, computers);
                answer++;
            }
        }
        return answer;
    }
    
    private void dfs(int idx, int[][] computers) {
        if(visit[idx] == 0) {
            visit[idx] =1;
            for(int i=0; i<computers[idx].length; i++) {
                if(computers[idx][i] ==1 && visit[i] ==0) {
                    dfs(i, computers);
                }
            }
        }
    }
}

 

코드 3

 

import java.util.HashSet;

class Solution { // find - union
    int[] parents;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        inItParents(n);
        for(int i=0; i<computers.length; i++) {
            for(int j=0; j<computers[i].length; j++) {
                if(computers[i][j] ==1) {
                    if(find(i) != find(j)) {
                        union(i,j);
                    }
                }
            }
        }
        
        HashSet<Integer> set = new HashSet<>();
        for(int num : parents) {
            set.add(find(num));
        }
        return set.size();
    }
    
    private void inItParents(int n) {
        parents = new int[n];
        for(int i=0; i<n; i++) {
            parents[i] = i;
        }
    }
    
    private int find(int val) {
        if(val == parents[val]) {
            return val;
        }
        return parents[val] = find(parents[val]);
    }
    
    private void union(int val1, int val2) {
        val1 = find(val1);
        val2 = find(val2);
        if(val1 != val2) {
            parents[val2] = val1;
        }
    }
}