[프로그래머스] 네트워크-JAVA

문제 링크

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

코딩테스트 연습 - 네트워크

 

BFS(너비우선탐색) 방식으로 풀이하였다.

풀이 방식

 

1. ArrayList에 컴퓨터 0~N까지 모두 넣는다.

2. 반복문을 돌리며 ArrayList에 첫번째 원소를 꺼낸다. (0번 컴퓨터)
   0 번째 컴퓨터부터 자신과 연결되어 있는 컴퓨터들을 queue에 넣는다.
   (ex. computers[0][1] == 1 이면, 0번째와 1번째 컴퓨터가 연결되어있는 것임)

3. queue에는 연결되어있는 모든 컴퓨터가 담겨있다.

4. 연결된 컴퓨터들, 즉 큐에 있는 원소들을 ArrayList에 있는 컴퓨터들과 대조하여 ArrayList원소를 삭제한다. 이 때 큐도 poll작업을 통해 원소들을 제거한다.

5. 네트워크 연결수를 +1 해준다. (answer + 1)

6. 2번~5번 로직을 반복한다. ArrayList에 원소가 없을 때 까지 반복한다.
   (만약 0, 3, 4, 5번 컴퓨터가 연결되어있다면 2번로직에서는 1번 컴퓨터가 나오게 된다.)

 

// 너비우선탐색
import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList;
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        Queue<Integer> bfs = new LinkedList<>();
        ArrayList<Integer> num = new ArrayList<>();
        
        for (int i = 0; i < computers.length; i++)
            num.add(i);
        while(num.size() != 0) {
            bfs.add(num.get(0));
            while (bfs.size() != 0) {
                for (int i = 0; i < num.size(); i++) {
                    if(bfs.peek() != num.get(i) && computers[bfs.peek()][num.get(i)] == 1)
                        bfs.add(num.get(i));
                }
                num.remove(Integer.valueOf(bfs.poll()));
            }
            answer++;
        }
        return answer;
    }
}

사실, 이 문제는 서로소 집합을 이용해서도 풀 수 있다.

union을 통해 연결된 컴퓨터를 집합에 추가시키고, find를 통해 부모를 찾고..

이 방식으로 풀이해보고 싶다면 이곳의 게시글을 참고해보자!