[프로그래머스] 네트워크

네트워크

풀이

• 전형적인 bfs/dfs
• 2차원 배열로 연결관계 주어지는데 List[] 로 빼서 구현했다.(답이 나오긴 했는데 굳이....,,,, ? 일을 두번 한 느낌 짜기전에 한번 더 생각하자^^)
• list[i].length 인지 list[i].size() 인지 헷갈렸음 ㅎㅎ;;

코드

1) bfs

import java.util.*;
import java.io.*;
class Solution {
    static int answer;
    static boolean[] visited;
    static List[] list;
    static int n;
    public int solution(int n, int[][] computers) {
        answer = 0;
        this.n = n;
        visited = new boolean[n];
        list = new List[n]; 
        for(int i=0;i<n;i++){
            list[i] = new LinkedList<>();
        }
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(computers[i][j]==1 && i!=j){
                    list[i].add(j);
                }
            }
        }
        
        for(int i=0;i<n;i++){
            if(!visited[i]){
                bfs(i);
                answer++;
            }
        }
        
        
        
        return answer;
    }
    
    public void bfs(int i){
        visited[i] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        while(!queue.isEmpty()){
            int now = queue.poll();
            for(int k=0;k<list[now].size();k++){
                int next = (int)list[now].get(k);
                if(!visited[next]){
                    visited[next] = true;
                    queue.add(next);
                }
            }
        }
    }
}

2) dfs, List[] 안쓰고

import java.util.*;
import java.io.*;
class Solution {
    static boolean[] visited;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n];
        
        for(int i=0;i<n;i++){
            if(!visited[i]){
                dfs(i,computers);
                answer++;
            }
        }
        return answer;
    }
    
    public void dfs(int i,int[][] computers){
        visited[i] = true;
        for(int k=0;k<computers.length;k++){
            if(!visited[k] && computers[i][k]==1){
                dfs(k,computers);
            }
        }
    }
    
    
}