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

네트워크 알고리즘 설명

문제 설명

주어진 컴퓨터 네트워크 정보로 연결된 네트워크의 수를 찾는 문제다. 각 컴퓨터가 네트워크 상에서 연결된 경우 하나의 네트워크로 간주한다. 이를 통해 네트워크의 개수를 계산한다.

해결 방법

1. 기본 설정:
   • visit 배열을 통해 각 노드의 방문 여부를 추적한다.
   • 모든 노드를 초기화하여 방문하지 않은 상태로 설정한다.

   static boolean[] visit;
   public int solution(int n, int[][] computers) {
       int answer = 0;
       visit = new boolean[n];
       for(int i = 0; i < n; i++) {
           visit[i] = false;
       }

2. 그래프 순회:
   • 각 노드를 순회하며 방문되지 않은 노드를 찾는다.
   • 방문되지 않은 노드가 발견되면 DFS를 수행하여 해당 노드와 연결된 모든 노드를 방문 처리한다.

   for (int graph = 0; graph < computers.length; graph++) {
       for (int node = 0; node < computers[0].length; node++) {
           if (computers[graph][node] == 1 && visit[node] == false) {
               visit[node] = true;
               answer++;
               dfs(computers, node);
           }
       }
   }

   for (int graph = 0; graph < computers.length; graph++) { for (int node = 0; node < computers[0].length; node++) { if (computers[graph][node] == 1 && visit[node] == false) { visit[node] = true; answer++; dfs(computers, node); } } }
3. 깊이 우선 탐색 (DFS):
   • 스택을 이용하여 DFS를 수행한다.
   • 시작 노드를 스택에 추가하고 방문 처리를 한다.
   • 스택이 비어있지 않은 동안 노드를 팝하고, 연결된 모든 노드를 탐색하여 방문되지 않은 노드를 스택에 추가하고 방문 처리한다.

   static void dfs(int[][] computers, int start) {
       Stack<Integer> stack = new Stack<>();
       stack.push(start);
       visit[start] = true;
       
       while (!stack.isEmpty()) {
           int n = stack.pop();
           
           for (int node = 0; node < computers[n].length; node++) {
               if (node == n) continue;
               if (computers[n][node] == 1 && visit[node] == false) {
                   visit[node] = true;
                   stack.push(node);
               }
           }
       }
   }

   
   
   

전체 코드 구현

import java.util.*;

class Solution {
    static boolean[] visit;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visit = new boolean[n];
        for(int i = 0; i < n; i++) {
            visit[i] = false;
        }
        // step1. 그래프 사이즈까지 순회
        for(int graph = 0; graph < computers.length; graph++) {
            // step2. 그래프에 연결된 노드를 모두 탐색
            for(int node = 0; node < computers[0].length; node++) {
                if(computers[graph][node] == 1 && visit[node] == false) {
                    visit[node] = true;
                    answer++;
                    dfs(computers, node);
                }
            }
        }
        return answer;
    }
    static void dfs(int[][] computers, int start) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        visit[start] = true;
        
        while(!stack.isEmpty()) {
            int n = stack.pop();
            
            for(int node = 0; node < computers[n].length; node++) {
                if(node == n) continue;
                if(computers[n][node] == 1 && visit[node] == false) {
                    visit[node] = true;
                    stack.push(node);
                }
            }
        }
    }
}