[알고리즘] 프로그래머스 - 네트워크

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

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

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        boolean visited[] = new boolean[n];
        int answer = 0;      
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                answer += bfs(computers, visited, n, i);
            } 
        }
        return answer;
    }
    
    public int bfs(int[][] computers, boolean[] visited, int n, int start) {
        
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(start);
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            int temp = queue.poll();
            
            for (int i = 0; i < n; i++) {
                if (computers[temp][i] == 1 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
        return 1;
    }
    
  
        
    
}

 

어렵게 생각할 것 없이 간선이 서로 연결된 그래프의 덩어리 개수를 구하는 문제이다.

 

주어진 인접행렬을 가지고 모든 정점에 대해서 bfs함수가 돌아간 횟수를 구하면 된다.

 

단순 그래프 문제라서 visited를 2차원 배열로 만들 필요도 없이 1차원이면 된다.