study-8

https://programmers.co.kr/learn/courses/30/lessons/43162?language=java
DFS/BFS - 네트워크

1차 아이디어

1부터 n까지 컴퓨터를 차례대로 처리

• 해당 컴퓨터이름 Set을 만들고 연결될 컴퓨터를 추가
• 이전 컴퓨터이름의 Set에 해당 컴퓨터가 속해 있을경우 해당 set에 추가
• 만약 다른
• 양 방향 연결이기에 서로를 자식으로 가질 경우 해결
  
  

2차 아이디어

• boolean visited 배열을 만든다
• stack을 이용하여 dfs 진행한 후 아직 방문하지 않은 컴퓨터를 다시 push하고 dfs를 진행한다 dfs를 진행한 횟수가 네트워크의 갯수

최종코드

import java.util.Stack;

//https://programmers.co.kr/learn/courses/30/lessons/43162?language=java
public class Programmers_43162 {
    static int n=3;
    static int [][] computers = {{1, 1, 0},{1, 1, 0},{0, 0, 1}};
    static boolean [] visited = new boolean[computers.length];
    static Stack<Integer> s = new Stack<>();
    static int ret = 0;

    public static void main(String[] args) {
        //i를 push하고 computers[pop()]과 연결된 인덱스를 push
        //이 과정을 스택이 빌때 까지 반복하면 i와 연결된 모든 컴퓨터들은 방문됨으로 전환
        for( int i=0;i< visited.length;i++){
            if(!visited[i]){
                dfs(i);
                ret++;
            }
        }
        System.out.println(ret);
    }
    static void dfs(int computer){
        s.push(computer);
        while(!s.empty()){
            int next = s.pop();
            visited[next] = true;
            for( int i=0;i<computers[next].length;i++){
                if( computers[next][i] == 1 && visited[i] == false){
                    s.push(i);
                } else {
                    continue;
                }
            }
        }
    }
}