본문 바로가기

알고리즘 공부 및 문제 풀이/프로그래머스(PRO)

[pro] 프로그래머스 level3 43162 네트워크 (Java) - BFS

[문제]

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

[풀이]

단순한 BFS 문제. 

 

[코드]

 

import java.util.*;

class Solution {
    boolean[] visited;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        //네트워크의 개수를 return
        
        visited = new boolean[n];
        for(int i=0; i<n; i++){
            if(visited[i]) continue;
            answer += bfs(i, n, computers);
            
        }
        
        return answer;
    }
    
    public int bfs(int node, int n, int[][] computers){
        Queue<Integer> q = new LinkedList<>();
        
        visited[node] = true;
        q.add(node);
        
        while(!q.isEmpty()){
            int u = q.poll();     
            for(int i=0; i<n; i++){
                if(i==u) continue;
                if(visited[i]) continue;
                if(computers[u][i]==1 && computers[i][u]==1){
                    visited[i] = true;
                    q.add(i);
                }
            }   
        }
        
        return 1;
    }
}