[Algorithm] 프로그래머스_네트워크(JAVA)

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

프로그래머스

---

문제 이해 잘못해서 시간을 꽤 쓴 문제다.

 

처음엔 2차원 방문 배열이 필요하다고 생각했는데,

각 컴퓨터의 방문 여부만 체크하면 되므로 1차원 배열으로도 충분함을 깨달았다.

 

0~n번까지의 컴퓨터가 있다면

0번 컴퓨터부터 큐에 넣고 0번과 연결되어 있는 컴퓨터를 찾는다.

그 컴퓨터를 큐에 넣는다.

위 과정을 반복하는 로직을 구현하면 된다~

 

이때, 0-1, 0-3, 3-2 가 연결되어 있다면 하나의 네트워크이다.

computers : [[1, 1, 0, 1], [1, 1, 0, 0], [0, 0, 1, 1], [1, 0, 1, 1]]

return : 1

 

풀이는 아래와 같다.

import java.util.*;
class Solution {
    boolean[] visited;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n];
        
        for(int i = 0; i < n; i++){
            if(computers[i][i] == 1 && !visited[i]){
                answer++;
                bfs(i, n, computers);
            }
        }
        
        return answer;
    }
    
    void bfs(int x, int n, int[][] computers){
        visited[x] = true;
        
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        while(!q.isEmpty()){
            int target = q.poll();
            for(int i = 0; i < n; i++){
                if(!visited[i] && computers[i][target] == 1){
                    visited[i] = true;
                    q.add(i);
                }
            }
        }
        
    }
}