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

📌 문제 정보

• 출처: 문제 링크
• 난이도: ⭐⭐
• 문제 유형: DFS / BFS
• 사용 언어: Java

---

🔍 문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

---

💡 풀이 노트

• 문제는 네트워크(컴퓨터 연결) 구조를 보고 몇 개의 네트워크 그룹이 있는지 찾는 것
• 컴퓨터를 노드, 연결 상태를 간선으로 생각하면
  이 문제는 그래프의 연결 요소(Connected Components) 개수 세기 문제와 같다
• 그래프(Graph)를 인접 리스트(`List<Integer>[] graph`)로 표현
  • `computers[i][j] == 1` 이면서 `i != j`일 때, `i`번 노드와 `j`번 노드는 연결되어 있다고 봄
• 방문 배열(visited[])을 만들어 이미 방문한 노드는 다시 탐색하지 않게 함
• 전체 흐름
  1. `computers` 2차원 배열을 이용해 그래프를 구성
  2. 각 노드(컴퓨터)를 돌면서, 아직 방문하지 않은 노드가 있으면 `dfs`를 호출
     → 이 호출을 통해 연결된 모든 노드를 방문
  3. `dfs`가 한 번 끝날 때마다 네트워크 개수(answer)를 1 증가
• DFS(깊이 우선 탐색)를 사용해서
  • 현재 노드에서 연결된 모든 노드를 재귀적으로 방문

---

🚀 코드 (Java)

import java.util.*;

class Solution {
    private List<Integer>[] graph;
    private boolean[] visited;

    public int solution(int n, int[][] computers) {
        graph = new ArrayList[n];
        visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (computers[i][j] == 1 && i != j) {
                    graph[i].add(j);
                }
            }
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i);
                answer++;
            }
        }

        return answer;
    }

    private void dfs(int node) {
        visited[node] = true;
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    }
}

---

🖥 실행 결과

입력 & 출력

n	computers				return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

---

📌 깃허브 코드 저장소: https://github.com/glorypang/CodingTest