8. DFS & BFS - 네트워크

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

스택으로 DFS 진행

main 메서드

1. 첫번째 컴퓨터부터 마지막 컴퓨터까지 dfs메서드에 인자로 넣어 호출한다.
2. 네트워크를 이룬 컴퓨터의 경우는 넘어간다 dfs메서드에 넣어 호출한다.

코드

for( int i=0;i< visited.length;i++){
    if(visited[i])continue;
    dfs(i);
    ret++;
}

dfs 메서드

boolean [ ] visited = new boolean [ 컴퓨터의 갯수 ]

• 네트워크가 이루어진 컴퓨터를 나타내는 배열

선언부

void dfs ( int computer )
int computer : 몇번째 컴퓨터인지

구현부

1. 스택에서 꺼낸 컴퓨터와 연결된 컴퓨터들 중 스택에 한번도 안들어간 컴퓨터를 방문함으로 바꾸고 스택에 다시 넣는 과정을 반복한다 스택이 빌 때까지 반복한다.

• computer와 네트워크를 이루는 모든 컴퓨터들은 방문함으로 체크되기에 알 수 있다.

코드

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;
            }
        }
    }
}

프로그래머스용 코드

import java.util.Stack;

class Solution {
    int n;
    int [][] computers;
    boolean [] visited;
    Stack<Integer> s = new Stack<>();
    int ret = 0;
    public int solution(int n, int[][] computers) {
        this.n = n;
        this.computers = computers;
        this.visited = new boolean[computers.length];
        for( int i=0;i< visited.length;i++){
            if(visited[i])continue;
            dfs(i);
            ret++;
        }
        return ret;
    }

    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;
                }
            }
        }
    }
}