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

코드 힌트:

1. 그래프 탐색의 필요성:
   • 각 컴퓨터를 노드로 보고, 컴퓨터 간의 연결을 간선으로 생각하면, 네트워크의 수를 찾는 문제는 그래프에서 연결 요소의 수를 찾는 문제로 볼 수 있습니다.
2. 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS):
   • 한 컴퓨터에서 시작해 연결된 모든 컴퓨터를 탐색하고, 이미 탐색한 컴퓨터는 다시 탐색하지 않도록 표시합니다.
   • 새로운 컴퓨터에서 탐색을 시작할 때마다 새로운 네트워크가 하나 발견됩니다.
3. 방문 여부를 기록하는 배열:
   • 배열을 사용해 각 컴퓨터가 이미 탐색된 네트워크에 포함되어 있는지를 기록합니다.

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int result = 0;
        
        boolean[] visited = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                result++;
                dfs(computers, visited, i);  // DFS를 사용하여 연결된 모든 컴퓨터 방문
                // bfs(computers, visited, i); // BFS를 사용하여 연결된 모든 컴퓨터 방문
            }
        }
        
        return result;
    }
    
    // 깊이 우선 탐색 (DFS) 메서드
    static void dfs(int[][] computers, boolean[] visited, int node) {
        visited[node] = true;
        
        for (int i = 0; i < computers.length; i++) {
            if (i != node && !visited[i] && computers[node][i] == 1) {
                dfs(computers, visited, i);  // 재귀 호출을 통해 연결된 모든 컴퓨터 방문
            }
        }
    }
    
    // 너비 우선 탐색 (BFS) 메서드
    static void bfs(int[][] computers, boolean[] visited, int node) {
        visited[node] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        
        while (!queue.isEmpty()) {
            int currentNode = queue.poll();
            
            for (int i = 0; i < visited.length; i++) {
                if (currentNode != i && !visited[i] && computers[currentNode][i] == 1) {
                    visited[i] = true;
                    queue.add(i);  // 큐에 추가하여 연결된 모든 컴퓨터 방문
                }
            }
        }
    }
}

 

주석 제거

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int result = 0;
        
        boolean[] visited = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                result++;
                dfs(computers, visited, i); 
                // bfs(computers, visited, i); 
            }
        }
        
        return result;
    }
    
    static void dfs(int[][] computers, boolean[] visited, int node) {
        visited[node] = true;
        
        for (int i = 0; i < computers.length; i++) {
            if (i != node && !visited[i] && computers[node][i] == 1) {
                dfs(computers, visited, i); 
            }
        }
    }
    
    static void bfs(int[][] computers, boolean[] visited, int node) {
        visited[node] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        
        while (!queue.isEmpty()) {
            int currentNode = queue.poll();
            
            for (int i = 0; i < visited.length; i++) {
                if (currentNode != i && !visited[i] && computers[currentNode][i] == 1) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}