[Algorithm/Programmers] 자바 - 네트워크

문제	플랫폼	난이도	유형	풀이 링크	문제 링크
네트워크	Programmers	Level 3	DFS/BFS	풀이	문제

풀이

각 컴퓨터들의 연결 상태에 대한 문제입니다.
A와 C가 직접 연결되지 않더라도, A와 B, B와 C가 연결되어 있다면 A와 C도 간접적으로 연결된다고 판단합니다.

무향 그래프이고, 가중치는 없습니다.

방향은 없지만 이해를 돕기위해 그림을 살펴보자면,
각 컴퓨터는 스스로 연결되어 있고, 0과 2는 연결되어 있지 않지만, 0과 1, 1과 2가 연결된 상태이기 때문에 간접적으로 연결된 상태입니다.

따라서 0, 1, 2는 모두 연결되어 있으므로
현재 그림에서 네트워크는 1개입니다.

방향이 없기 때문에 0의 입장에서 1과 연결되어 있다면 1의 입장에서도 0과 연결되어 있습니다.
boolean[] checked를 사용하여 방문한 컴퓨터를 확인하도록 하겠습니다.

Case 1: DFS

class Solution {    
    public int solution(int n, int[][] computers) {
        
        boolean[] checked = new boolean[n];

        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!checked[i]) {
                dfs(n, computers, i, checked);
                count += 1;
            }
        }
        
        return count;
    }
    
    private boolean[] dfs(int n, int[][] computers, int depth, boolean[] checked) {

        checked[depth] = true;

        for (int i = 0; i < n; i++) {
            if(!checked[i] && depth != i && computers[depth][i] == 1)
                dfs(n, computers, i, checked);
        }

        return checked;
    }
}

Case 2: BFS

import java.util.*;

class Solution {    
    public int solution(int n, int[][] computers) {
        
        boolean[] checked = new boolean[n];

        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!checked[i]) {
                bfs(n, computers, i, checked);
                count += 1;
            }
        }
        
        return count;
    }
    
    private void bfs(int n, int[][] computers, int index, boolean[] checked) {
        Queue<Integer> q = new LinkedList<>();
        q.add(index);

        while (!q.isEmpty()) {
            int cur = q.poll();
            checked[cur] = true;

            for (int i = 0; i < n; i++) {
                if(!checked[i] && index != i && computers[cur][i] == 1)
                    q.add(i);
            }

        }

    }
 
}