간선 리스트로 연결된 정점의 그룹들의 수 찾기

문제

방향이 없는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.

 

 

입력값

2차 배열 정수요소 

ex) int[][]{{0,1}, {2,3}, {3,4}}

 

 

출력값

int 타입의 정점들이 연결된 그룹들의 수.

 

 

입출력 및 그래프 예시

int result = connectedVertices(new int[][]{
	{0, 1},
	{2, 3},
	{4, 5},
});
System.out.println(result); // 3

 

풀이 1 - DFS와 정점리스트 사용

class Solution { //DFS
    public int connectedVertices(int[][] edges) {
        int count = 0; // 재귀를돌며 정점들의 그룹의 수를 카운트업 하여 마지막에 반환
        
        ArrayList<Integer> visit = new ArrayList<>(); // DFS 순회시 중복방지를 위한 리스트

        // 간선리스트를 해시맵을 이용해 정점리스트로 변환
        HashMap<Integer, ArrayList<Integer>> hashmap = new HashMap<>();
        for(int[] edge: edges){
            if(!hashmap.containsKey(edge[0]))  hashmap.put(edge[0],new ArrayList<>());
            hashmap.get(edge[0]).add(edge[1]);

            if(!hashmap.containsKey(edge[1]))  hashmap.put(edge[1],new ArrayList<>());
            hashmap.get(edge[1]).add(edge[0]);
        }

        // 해시맵으로된 정점리스트의 반복문을 위해 key를 배열에 저장
        ArrayList<Integer> keyArr = new ArrayList<>();
        hashmap.keySet().forEach(a->keyArr.add(a));

        
        //본격적인 로직
        // 해시맵의 각 키당 반복문을 돌림
        for(int key : keyArr){
            
            //이미 순회를 마친 정점이라면 다른 정점과 연결되있다는 뜻이므로
            //만약 해시맵의 키값으로 저장된 정점을 순회했었다면 다음 키값으로 반복문이 넘어감
            if(!visit.contains(key)){
                count++; // 처음 순회하였다면 카운트업해주고
                visit = recursionDFS(key,visit,hashmap); //현재 키값, 중복리스트, 정점리스트를 매개인자로 재귀메서드 호출
                // 첫번째 키값에 저장된 정점들의 재귀가 모두 끝나면 다음 키값에 저장된 정점들을 이용하여 재귀를 호출하며
                // 만약 처음 반환된 중복리스트에 해당 정점이 등록되있다면 두번째 정점은 무시하고 세번째 정점으로 이동
            }
        }
        return count; 
    }
    ArrayList<Integer> recursionDFS(Integer currentVertex, ArrayList<Integer> visit, HashMap<Integer, ArrayList<Integer>> hashmap ){
        if(!hashmap.containsKey(currentVertex)) return visit; 
        
        visit.add((currentVertex)); //현재 재귀가 돌아가는 정점을 중복리스트에 추가, 이후 이 정점은 재귀를 돌지 않음

        //해시맵에 접근하여 현재 전달받은 키에 연결된 모든 정점들을 이용하여 
        //만약 중복리스트에 등록되지 않은 정점의 경우 재귀 호출, 이후 해당 재귀 메서드 내에서 중복리스트에 추가됨 
        hashmap.get(currentVertex).forEach(a->{
            if(!visit.contains(a)) recursionDFS(a,visit,hashmap);
        });

        // 모든 재귀가 끝나면 중복리스트 반환
        return visit;
    }

 

 

풀이2 - Queue를 이용한 BFS와 정점행렬 사용

public class Solution { //BFS
    public int connectedVertices(int[][] edges) {
        int count = 0;

        Queue<Integer> queue = new LinkedList<>();
        ArrayList<Integer> visit = new ArrayList<>();
        int max =0;

        for(int[] edge:edges){
            for(int vertex : edge) max = Math.max(max,vertex);
        }

        int[][] vertexMatrix = new int[max+1][max+1];

        for(int[] edge:edges){
            vertexMatrix[edge[0]][edge[1]] =1;
            vertexMatrix[edge[1]][edge[0]] =1;
        }
        for(int i=0; i<vertexMatrix.length; i++){

            if(!visit.contains(i)){
                count++;
                queue.add(i);
                visit = recursion(queue, visit,vertexMatrix);
            }
        }
        return count;
    }
    ArrayList<Integer> recursion(Queue<Integer> queue,ArrayList<Integer> visit, int[][] vertexMatrix){
        if(queue.isEmpty()) return visit;
        int currentVertex = queue.poll();

        if(!visit.contains(currentVertex)){
            visit.add(currentVertex);

            for(int i=0; i<vertexMatrix.length; i++){
                if(vertexMatrix[currentVertex][i]==1) queue.add(i);
            }
        }
        recursion(queue, visit, vertexMatrix);
        return visit;
    }
}

 

풀이1과 달리 정점리스트를 정점행렬로 사용해줫으며 BFS순회를 위해 Queue를 사용한것 이외에 큰 차이점은 없음