프로그래머스 - 네트워크

레벨3의 BFS 문제이다.

풀이
백준 그림 문제와 비슷하다.

• 2차원 배열에서 이어진 칸들인 그림을 세는 것처럼, 존재하는 컴퓨터들 중 이어진 컴퓨터들을 세면 된다.
• 그림 문제에선 2차원 배열에서 탐색한 칸에 1로 방문했다는 표시를 해주었는데, 여기서는 1차원 배열을 만들어서 탐색한 컴퓨터 번호에 해당하는 index에 표시해주었다.
• 그리고 그림에서 방문한 칸의 좌표인 Pair클래스를 Queue에 넣어주는 것처럼, 방문한 Computer클래스를 Queue에 넣어주었다.
• Computer클래스는 자신의 번호와 자신과 이어진 컴퓨터들 정보를 가지고 있다.
• 디테일은 코드 참고

import java.util.*;
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        //n, computers
        //각 i번 컴퓨터는, 그 i의 j번과 연결되면 1 or 0
        //i, i 즉 자기자신과 자기자신은 항상 1
        //1. 컴퓨터리스트(모든컴퓨터를) 순서대로 탐색
        //2. 한 컴퓨터와 이어진 것 다 탐색하면서 컴퓨터리스트에서 제거
        //3. 하나의 네트워크가 끝나면 answer++
        //4. 컴퓨터리스트가 빌때까지 반복, return answer
        int[] isUsed = new int[computers.length];
        for(int i = 0; i < computers.length; i++){
        	//한 번 방문한 컴퓨터면 continue
            if(isUsed[i] == 1){
                continue;
            }
            Queue<Computer> queue = new LinkedList<>();
            //현재 컴퓨터를 queue에 add 후 bfs시작 (connection 탐색시작)
            queue.add(new Computer(i, computers[i]));
            //방문 표시
            isUsed[i] = 1;
            while(!queue.isEmpty()){
                Computer now = queue.poll();
                //현재 컴퓨터에 연결되어있는 모든 컴퓨터 add, isUsed = 1
                for(int j = 0; j < n; j++){
                    //자기자신이면 continue _computers[i][i]인 경우
                    if(j == i){
                        continue;
                    }
                    //한 번 방문한 컴퓨터면 continue
                    if(isUsed[j] == 1){
                        continue;
                    }
                    //현재 컴퓨터의 j번index가 1이면 연결됨
                    if(now.connections[j] != 1){
                        continue;
                    }
                    queue.add(new Computer(j, computers[j]));
                    isUsed[j] = 1;
                }
            }
            //하나의 connection bfs탐색 완료, connection 1추가
            answer++;
        }
        return answer;
    }
    public class Computer{
        int index;
        int[] connections;
        Computer(int index, int[] connections){
            this.index = index;
            this.connections = connections;
        }
    }
}