출처

해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다

---

문제

문제 분석

네트워크가 의미하는 바가 무엇인지를 아는것이 중요한 문제입니다. 컴퓨터들의 묶음으로 결국 네트워크가 몇개냐는 의미는 컴퓨터들이 몇개의 묶음으로 구성되는 지 구하는 문제입니다.

---

풀이

나의 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        List<Integer> left = new ArrayList<>();
        for(int i = 0; i < n; i++) left.add(i);
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        
        
        while(!left.isEmpty()){
            int now = left.get(0);
            left.remove(0);
            
            System.out.println(now);
            
            queue.offer(now);
            visited[now] = true;
                
            while(!queue.isEmpty()){
                int node = queue.poll();
                for(int adjacent = 0; adjacent < computers[node].length; adjacent++){
                    if(computers[node][adjacent] == 1 && visited[adjacent] == false){
                        queue.offer(adjacent);
                        visited[node] = true;
                    }
                }
                left.remove(new Integer(node));
            }
            
            answer++;
        }
        
        return answer;
    }
}

전체 컴퓨터들의 목록을 List로 관리하였고

이중 while문을 통해 내부적으로 BFS를 포함시켜 네트워크 내 컴퓨터들을 모두 순회할 수 있도록 하였습니다.

네트워크내 에서 컴퓨터를 방문하면 List 목록에서도 제거하며 남은 컴퓨터 목록이 사라질 때까지 네트워크 순회를 진행 하였습니다.

강의의 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n]; //방문 여부
        
        //컴퓨터 하나씩 네트워크 검색
        for(int i = 0 ; i < computers.length; i++){
            if(visited[i]) continue; //이미 방문한 적이 있는 컴퓨터는 패스
            answer++; //네트워크 갯수 추가
            visitAllConnectedComputers(computers,visited,i); //연결된 컴퓨터 모두 방문
        }
        return answer;
    }
    
    //네트워크 내 컴퓨터 모두 방문(BFS)
    void visitAllConnectedComputers(final int[][] computers, boolean[] visited, int c){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(c);
        
        while(!queue.isEmpty()){
            int computer = queue.poll();
            for(int adjacent = 0; adjacent < computers[computer].length; adjacent++){
                if(visited[adjacent]) continue;
                if(computers[computer][adjacent] == 1){
               		visited[adjacent] = true;
                	queue.offer(adjacent);
                }
            }
        }
    }
}

제가 풀었던 내부 while(!queue.isEmpty())문이 함수로 따로 빼낸것을 제외하고는 로직이 같습니다. 아직 방문 안했는 컴퓨터를 찾고, 해당 컴퓨터가 속한 네트워크내의 모든 컴퓨터들을 조회합니다.

결과적으로 여태 방문했던 네트워크들에 속했던 컴퓨터들을 제외한 컴퓨터들만 선택되어 다시 네트워크를 순회하며 모든 컴퓨터들을 순회할 것입니다.

---

Github

https://github.com/ds02168/Study_Algorithm/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%5BJava%5D%20%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/%ED%8C%8C%ED%8A%B88.%EA%B7%B8%EB%9E%98%ED%94%84%2CDFS%2CBFS/%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC.java