프로그래머스(Programmers) : 네트워크

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

프로그래머스

이번 문제는 BFS/DFS 문제인 Network 문제이다.

처음에 봤을 때는 위상 정렬로 푸는 것이 나은 선택인가 싶었지만, 위상정렬로 풀었을 때 양방향이라서 문제가 될것 같았다.

 

BFS/DFS 자체는 이제 코드가 써질만큼 쉽긴 했는데, Q에 넣는 조건을 헷갈려 시간이 좀 걸렸다.

 

풀고나서 보니 분명 더 최적화할 수 있는 요소가 있을 것 같은데...

 

구해야할 것

주어진 모든 정점의 네트워크

전제 및 고려사항

연결되지 않았더라도 해당 정점을 확인해야 한다

 

1. 네트워크를 인접리스트로 만들어 초기화 한다.

2. computers 2차원 배열에 있는 값들을 네트워크 인접리스트로 전체를 초기화한다.

3. 방문 배열을 초기화한다.

4. BFS를 돌린다.

이때, 방문한 정점은 없애며, 방문하지 않은 정점만 배열에 넣어서 확인한다.

 

아래는 코드 전문이다.

import java.util.*;
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        List<Integer>[] network=new ArrayList[n];
        
        for(int i=0;i<n;i++){
            network[i]=new ArrayList<Integer>();
        }         
//         네트워크 연결 초기화
        for(int row=0;row<computers.length;row++){
            for(int col=0;col<computers[row].length;col++){
                if(row!=col&&computers[row][col]==1){
                    network[row].add(col);
                }
            }
        }
//      방문 배열 초기화
        boolean[] vis=new boolean[n];
        
        for(int vertex=0;vertex<n;vertex++){
            if(vis[vertex])
                continue;
            else{
                Queue<Integer> q=new ArrayDeque<Integer>();
                                    
                q.offer(vertex);
                answer++;
                
                while(!q.isEmpty()){
                    int poll=q.poll();
                    
                    if(vis[poll])
                        continue;
                    
                    vis[poll]=true;

                    
                    for(int i=0;i<network[poll].size();i++){
                        if(!vis[network[poll].get(i)])
                            q.offer(network[poll].get(i));
                    }
                }
            }                
        }
        
        
        return answer;
    }
}