[프로그래머스] 네트워크 (자바 풀이)

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

📌 문제

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다

 

 

예시 

3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 

---

 

 

 

👀 문제 해석

 

이 문제는 주어진 연결 정보를 바탕으로 서로 통신할 수 있는 컴퓨터들이 몇 개의 네트워크로 나누어지는지를 판단하는 문제이다. 즉, 각 컴퓨터가 서로 직접적 혹은 간접적으로 연결되어 있다면 하나의 네트워크로 묶을 수 있으며, 이렇게 묶을 수 있는 네트워크의 총 개수를 구하는 것이 목표이다.

 

입력으로 주어진 2차원 배열 computers[i][j]는 i번 컴퓨터와 j번 컴퓨터가 직접 연결되었는지를 나타낸다. 값이 1이면 연결된 것이고, 0이면 연결되지 않은 것이다. 예를 들어, computers[0][1] = 1이면 0번 컴퓨터와 1번 컴퓨터가 직접 연결되어 있다는 의미다.

 

컴퓨터들이 서로 연결된 관계를 판단해야 하므로 이 문제는 그래프 탐색 알고리즘으로 분류할 수 있다. 더 정확히 말하면, 연결된 컴퓨터끼리 묶음을 찾는 DFS 또는 BFS 로 접근 가능한 문제다. 각 컴퓨터를 노드(node), 직접 연결된 컴퓨터끼리의 관계를 간선(edge)으로 보고, 그래프에서 독립적인 그룹의 개수를 구하는 문제라고 이해하면 쉽다.

 

정리하면 이 문제는 그래프 탐색 알고리즘을 활용하여, 주어진 연결 정보를 바탕으로 네트워크의 개수를 찾아내는 문제이다.

 

 

🔎 접근

이 문제를 처음 접했을 때, 머릿속에서 다음과 같은 순서로 아이디어가 스치고 지나갔다.

 

1) Union-Find가 떠오름

 

“컴퓨터들이 서로 연결되어 있다”라는 설명을 보자마자, 서로 다른 집합을 합치고 루트를 찾는 Disjoint-Set Union이 바로 생각났다. 그런데 유니온 파인드? 흠...

 

곰곰이 고민해보니

1) find와 union을 위해 부모 배열과 랭크 배열을 초기화하고,

2) 매번 인접 행렬을 훑으며 union(i,j)을 호출해야 해서

3) 코드가 복잡해지고 오히려 가독성이 떨어질 것 같았다.

 

그래서 Union-Find는 일단 보류.

 

2) DFS 아이디어 검토

 

그 다음은 프로그래머스 유형에서 이미 힌트가 있기도 하거니와 “그래프 탐색” 문제이기도 하므로 DFS 또는 BFS로 풀어야겠다고 생각할 수 있었다. 

 

그런데 문제는,

• 문제에서 주어지는 건 인접 행렬(computers[][]) 형태라,
• “어떤 정점부터 어떻게 재귀 호출을 시작해야 할지”
• 그리고 “분리된 덩어리(네트워크)를 모두 처리하려면?”

과 같은 세부 로직이 바로 떠오르지가 않았다.

 

3) 뭉텅이로 처리하기(멀티 DFS) 고민

 

하나의 DFS로는 오직 한 개의 연결 요소만 탐색할 수 있으므로, “네트워크가 여러 개일 때 어떻게 반복해야 하나”가 헷갈렸다. 결국, 모든 정점을 순회하며 아직 방문되지 않은 곳에서 DFS를 다시 시작하는 패턴을 떠올려야만 했다.

 

결론:

1. Union-Find는 개념상 가능하지만, 오히려 오버헤드가 크고
2. DFS도 처음엔 떠올리기 어려웠으나, “한 덩어리씩 색칠하듯 방문 처리 → 남은 정점 또 시작” 패턴이 핵심임을 깨닫는 것이 문제 해석의 핵심

 

 

 

💡 풀이 아이디어 

 

연결된 컴퓨터 집합을 하나의 덩어리로 보고, 각 덩어리를 색칠하듯이 방문 처리하는 방식으로 접근하는 것이 핵심이다.

 

각각의 컴퓨터는 점(●)으로, 컴퓨터 간 연결을 선(—)으로 그려놓고 생각해 보자.

 

처음에, 색칠되지 않은 컴퓨터 하나를 선택하고, 특정한 색깔로 색칠한다고 생각한다. 그리고 그 컴퓨터와 직접 혹은 간접적으로 연결된 모든 컴퓨터들을 같은 색으로 칠해나간다. 이렇게 연결된 컴퓨터를 전부 색칠하면 하나의 네트워크가 완성된 것이다.

 

하나의 네트워크 색칠이 끝나면, 아직 색칠되지 않은 다른 컴퓨터를 선택하여 새로운 색으로 또 다시 색칠을 시작한다. 이런 과정을 모든 컴퓨터가 색칠될 때까지 반복하면, 결국 몇 개의 색을 사용했는지가 바로 네트워크의 개수가 된다.

 

예를 들면 다음과 같다.

 

초기 상태

●──●   ●
0   1   2

• 모든 컴퓨터는 아직 색칠되지 않은 상태이다.

1단계: 첫 번째 네트워크 색칠 시작

• 먼저, 색칠되지 않은 0번 컴퓨터에서 시작하여 빨간색으로 칠한다.
• 0번과 연결된 컴퓨터(1번)로 이동해서 같은 빨간색으로 칠한다.
• 1번과 연결된 다른 컴퓨터가 없으므로 이 네트워크 색칠은 여기서 끝난다.

🔴──🔴   ●
 0    1    2

• 이렇게 빨간색으로 칠해진 부분이 첫 번째 네트워크가 된다.

2단계: 두 번째 네트워크 색칠 시작

• 아직 색칠되지 않은 컴퓨터(2번)를 골라 새로운 색깔(파랑)로 칠한다.
• 2번 컴퓨터는 다른 컴퓨터와 연결되어 있지 않으므로 바로 색칠을 끝낸다.

🔴──🔴   🔵
 0    1    2

• 이렇게 파란색으로 칠해진 컴퓨터가 두 번째 네트워크가 된다.

이렇게, 색칠을 시작한 횟수는 두 번이므로, 주어진 예제의 네트워크 개수는 2개가 된다.

 

즉, 색칠을 시작할 때마다 네트워크를 하나씩 찾는 문제가 되는 것이다.

 

graph LR
  subgraph "네트워크 1"
    0((0)) --- 1((1))
    style 0 fill:#ff9999
    style 1 fill:#ff9999
  end
  subgraph "네트워크 2"
    2((2))
    style 2 fill:#99ccff
  end

 

 

이것을 DFS 알고리즘으로 적용할 수 있을까?

 

우선, 모든 컴퓨터의 방문 여부를 기록하기 위해 visited 배열을 준비한다. 이는 색칠 놀이에서 각 컴퓨터가 "색칠되었는지 아닌지"를 확인하는 용도로 사용된다. 처음엔 모든 컴퓨터가 아직 칠해지지 않은 상태로, 즉 모두 false 상태로 초기화된다. 또한, 몇 개의 네트워크가 존재하는지 개수를 세기 위해 count 변수를 0으로 초기화해 둔다.

 

이제, 0번 컴퓨터부터 마지막 컴퓨터까지 순차적으로 살펴보며, 아직 색칠되지 않은 컴퓨터(즉, visited[i] == false)를 찾으면 새로운 네트워크가 발견된 것이므로 count를 1 증가시킨다. 이는 마치 색칠 놀이에서 새로운 색깔로 색칠을 시작하는 순간과 같다.

 

이 시점에서 깊이 우선 탐색(DFS)을 호출하게 된다. DFS를 호출하는 과정은 색칠 놀이에서 붓을 한 번 대어 색칠을 시작하는 과정과 똑같다. 즉, DFS는 붓으로 물감이 점에서부터 번져나가듯, 현재 선택된 컴퓨터로부터 연결된 모든 컴퓨터를 재귀적으로 탐색하며 같은 색으로 색칠한다(방문 처리).

 

그런데 다시 생각해 보자. 

 

문제에서 주어진 입력을 생각해 볼 때, 노드와 간선으로 주어지지 않았다. 그런데 어떻게 어떤 게 컴퓨터고, 그 컴퓨터에서 다른 컴퓨터로 이어 간다는 게 도대체 어떻게 가능한 것일까? 

 

이 문제에서는 컴퓨터들 간의 연결 관계가 computers라는 인접 행렬의 형태로 주어진다.

 

주어진 예시를 살펴 보면, 

 

computers = [
  [1, 1, 0],
  [1, 1, 0],
  [0, 0, 1]
]

 

이 행렬의 의미는 다음과 같다.

• computers[i][j] 값이 1이라면, i번 컴퓨터와 j번 컴퓨터가 직접 연결되어 있다는 뜻
• 값이 0이라면 연결되어 있지 않다는 뜻
• 또한, 각 컴퓨터는 자기 자신과 항상 연결되어 있으므로 대각선 값인 computers[i][i]는 항상 1

이를 실제 컴퓨터 연결 관계로 시각화하면,

컴퓨터 0번은 자신(0번)과 연결되어 있고, 컴퓨터 1번과 연결되어 있다.
컴퓨터 1번도 자신(1번)과 연결되어 있고, 컴퓨터 0번과 연결되어 있다.
컴퓨터 2번은 오직 자기 자신과만 연결되어 있고, 다른 컴퓨터와 연결이 없다.

이것은 곧 다음과 같은 그림이 된다. 

graph LR
  0((0)) --- 1((1))
  2((2))

 

이 그림은 앞서 우리가 색칠 놀이로 예시를 들었던 것과 정확히 동일한 형태이다. 즉, 인접 행렬의 각 값은 실제 그래프에서 노드(컴퓨터) 사이의 연결 여부를 나타낸다. 따라서 우리는 이 행렬을 순회하면서 각 컴퓨터가 서로 직접적으로 연결되어 있는지를 확인하고, 연결된 컴퓨터로 DFS를 호출하여 한 네트워크씩 방문(색칠) 처리를 하면 되는 것이다.

 

즉, 입력값으로 주어진 인접 행렬이 곧 그래프이며, DFS는 이 인접 행렬을 기반으로 각 노드(컴퓨터)에서 다른 노드로 연결된 길(간선)을 찾아 이동하면서 방문 처리를 하는 알고리즘이라고 이해할 수 있다.

• 각 컴퓨터(노드): computers 배열의 각 인덱스(0, 1, 2, ...)
• 컴퓨터 간의 연결(간선): computers[i][j]의 값이 1일 때 i ↔︎ j 연결됨

여기서 헷갈릴 수 있는데, n이 DFS의 순회 횟수라는 말은 모든 컴퓨터를 한번씩 방문할 기회를 가진다는 의미이다. DFS는 하나의 컴퓨터에서 시작하여 연결된 모든 컴퓨터를 탐색하고, 방문한 컴퓨터는 다시 방문하지 않기 때문에, 결국 전체적으로 최대 n개의 DFS 탐색 기회가 주어지게 되는 것이다.

 

하지만 실제로는 모든 컴퓨터가 이미 한 번씩 방문 처리가 되었기 때문에(즉, 이미 색칠된 상태), DFS를 호출하더라도 즉시 종료된다. 다시 색칠 놀이 비유를 가져와 보자면, 이미 한 번 빨간색으로 완벽하게 칠해진 영역에 다른 붓을 가져다 대더라도 추가로 칠할 곳이 없으므로 아무 변화 없이 종료되는 것과 같다.

 

결국, DFS를 최대 n번 호출하지만, 실질적으로 탐색(색칠)이 이루어지는 횟수는 정확히 연결 요소(네트워크)의 개수만큼이며, 나머지 호출들은 이미 방문된(색칠된) 상태를 확인하고 바로 종료된다. 즉, DFS를 호출한 횟수 자체가 중요한 것이 아니라, 그 호출이 실제로 새로운 영역(아직 방문하지 않은 컴퓨터)을 탐색하는지 여부가 중요하다.

 

이 개념이 핵심이다. DFS 호출 횟수와 실제 탐색되는 네트워크 수가 구분되는 지점을 이해하는 것이 이 문제를 정확히 이해하는 중요한 포인트이다.

 

마지막으로 알고리즘 내부의 표현이 어떻게 될지 간략하게만 짚어보면, 

 

새로운 네트워크가 시작된 지점에서 DFS를 호출하면, 현재 컴퓨터에서 연결된 컴퓨터들을 순서대로 확인하며(computers[u][v] == 1인 경우), 아직 방문되지 않았다면 (visited[v] == false), 그 컴퓨터를 방문 처리, 즉 노드에 "색깔이 칠해진다". 그리고 다시 그 컴퓨터를 기준으로 DFS를 재귀 호출하는 방식으로 동작한다. 이렇게 하면 마치 붓으로 물감이 퍼지듯이 그 컴퓨터와 직접 또는 간접적으로 연결된 모든 컴퓨터가 한 번에 같은 색으로 “칠해진다”.  

 

이렇게 한 번의 DFS 호출이 끝나면, 연결된 모든 컴퓨터(한 네트워크)가 완전히 색칠된 상태가 된다. 그리고 다시 색칠되지 않은 컴퓨터가 남아 있다면, 그 컴퓨터에서 다시 새로운 DFS를 시작한다. 이를 반복하면 결국 모든 컴퓨터들이 방문 처리(색칠 완료)되며, 최종적으로는 count 값이 바로 네트워크의 총 개수가 된다.

 

 

🚀 풀이 코드 구현 

 

 

package template.programmers;

import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.Nested;
import org.junit.jupiter.api.Test;

class Solution {
	public int solution(int n, int[][] computers) {
		boolean[] visited = new boolean[n];
		int answer = 0;
		for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				answer++;
				dfs(i, computers, visited);
			}
		}
		return answer;
	}

	private void dfs(int u, int[][] computers, boolean[] visited) {
		visited[u] = true;
		for (int v = 0; v < computers.length; v++) {
			if (computers[u][v] == 1 && !visited[v]) {
				dfs(v, computers, visited);
			}
		}
	}

	@Nested
	class WordChainTests {

		@Test
		public void test() {
			Solution s = new Solution();
			assertEquals(2, s.solution(3, new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));
			assertEquals(1, s.solution(3, new int[][]{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}}));
		}

	}
}

 

❄️ 풀이 코드 설명 

위에서 살펴본 색칠 놀이 비유를 코드로 옮기면, 크게 세 부분으로 나눌 수 있다:

1. 방문 여부를 기록하는 배열 초기화
2. 모든 컴퓨터(정점)를 순회하며 색칠(DFS) 시작
3. 한 덩어리가 다 칠해질 때마다 네트워크 개수 세기

1. 방문 체크용 visited 배열과 count 변수

boolean[] visited = new boolean[n];
int answer = 0;

• visited[i] == false는 “아직 색칠되지 않은 점”을 의미한다.
• answer는 붓을 든 횟수, 즉 네트워크 개수를 센다.

2. 모든 정점 순회하며 새로운 색칠(DFS) 시작

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

• i번째 컴퓨터가 아직 색칠되지 않았다면,
  1. 새로운 네트워크를 발견한 것이므로 answer++
  2. dfs(i, …)를 호출해 붓을 한번 대고 물감이 퍼지듯 칠하기 시작

3. 연결된 컴퓨터를 몽땅 칠하는 dfs 메서드

private void dfs(int u, int[][] computers, boolean[] visited) {
    visited[u] = true;
    for (int v = 0; v < computers.length; v++) {
        if (computers[u][v] == 1 && !visited[v]) {
            dfs(v, computers, visited);
        }
    }
}

• 1단계: 현재 컴퓨터 u를 방문(visited[u]=true) → 붓으로 칠하기
• 2단계: 인접 행렬(computers[u][v])을 순회하며
  • == 1인 경우만 “선(연결)”이 있다는 뜻
  • 그리고 아직 색칠되지 않은(!visited[v]) 컴퓨터가 있으면
    • 재귀 호출로 다시 그 컴퓨터를 칠하러 들어간다
• 이렇게 재귀가 더 이상 신규 방문할 곳이 없을 때까지 퍼져 나가며,
  한 덩어리(네트워크)에 속한 모든 컴퓨터를 “한 번에” 칠해준다.

dfs 메서드가 재귀로 호출될 때, 데이터 흐름이 어떻게 확인되는지 i=0인 케이스만 한 번 살펴보자.

 

아래와 같은 기본 세팅에서, 

 

int n = 3;
int[][] computers = {
  {1, 1, 0},
  {1, 1, 1},
  {0, 1, 1}
};
boolean[] visited = new boolean[]{false, false, false};
int answer = 0;

 

 

 

1) 외부 루프 시작 (i = 0)

• visited[0] == false 이므로
  • answer를 1로 올리고
  • dfs(0) 호출

answer = 1
call dfs(0)

 

2) dfs(0) 들어가기

• 지금 스택: dfs(0)
• 방문 처리: visited[0] = true
  → visited = [T, F, F]
• 인접 행렬 순회:
  • v = 0 → computers[0][0] == 1 이지만 visited[0] 이미 true → skip
  • v = 1 → computers[0][1] == 1 && visited[1] == false
    → dfs(1) 재귀 호출

visited: [T, F, F]
stack: dfs(0) → dfs(1)

 

3) dfs(1) 들어가기

• 지금 스택: dfs(0) → dfs(1)
• 방문 처리: visited[1] = true
  → visited = [T, T, F]
• 인접 행렬 순회:
  • v = 0 → computers[1][0] == 1 but visited[0] == true → skip
  • v = 1 → computers[1][1] == 1 but visited[1] == true → skip
  • v = 2 → computers[1][2] == 1 && visited[2] == false
    → dfs(2) 재귀 호출

visited: [T, T, F]
stack: dfs(0) → dfs(1) → dfs(2)

 

4) dfs(2) 들어가기

• 지금 스택: dfs(0) → dfs(1) → dfs(2)
• 방문 처리: visited[2] = true
  → visited = [T, T, T]
• 인접 행렬 순회:
  • v = 0,1,2 모두 visited 또는 연결 안 됨 → 재귀 종료

visited: [T, T, T]
return from dfs(2)
stack: dfs(0) → dfs(1)

 

5) dfs(1)로 복귀

• 남은 v 값 없음 → 종료

return from dfs(1)
stack: dfs(0)

6) dfs(0)로 복귀

• 남은 v 값 없음 → 종료

return from dfs(0)
stack: (empty)

 

 

 

☘️ 시간 복잡도 

 

마지막으로 시간 복잡도는 어떻게 될까? 

 

1) 외부 루프

• 0번부터 (n-1)번까지 모든 컴퓨터를 한 번씩 순회하며 visited[i]를 확인 → O(n)

2) DFS 호출 및 내부 순회

• 실제로 각 컴퓨터를 방문할 때마다 그 행의 연결 관계를 나타내는 길이 n인 배열을 끝까지 훑는다.
• 각 컴퓨터에 대해 최대 한 번 방문 처리되므로, 전체적으로 인접 행렬의 모든 칸을 한 번씩 살피는 형태 → O(n^2)

따라서 전체적인 시간 복잡도는 최악의 경우 O(n²), 그런데 문제 데이터에서 n이 사실 200으로 상당히 작으므로 풀이에는 문제 없음.