문제 링크
1. 아이디어
연결 관계로 이어진 컴퓨터의 덩어리, 즉 그래프의 연결 요소 개수를 세는 문제다. computers는 대칭 인접 행렬이고 대각 원소는 항상 1이다.
BFS·DFS 풀이는 방문하지 않은 정점을 하나 잡아 그 정점에서 도달 가능한 모든 정점을 표시하는 탐색을 한 번 돌리고 네트워크를 찾았다는 의미로 카운트를 1 늘린다. 아직 방문 안 된 정점이 남아 있다는 것은 새로운 네트워크가 있다는 뜻이므로, 전체 정점을 훑으며 탐색을 시작한 횟수가 곧 네트워크 수다.
네트워크의 수가 그래프에서 연결 관계로 이어진 덩어리의 수라는 점에서 Union-Find를 활용해 서로소 집합의 수를 세는 방식으로도 해결할 수 있다. computers[i][j]가 1인 모든 쌍을 union하고, 마지막에 자기 자신이 대표인 정점의 수를 센다.
2. 복잡도
| 접근 | 시간 | 공간 |
|---|
| BFS | $O(N^2)$ | $O(N)$ |
| DFS | $O(N^2)$ | $O(N)$ |
| Union-Find | $O(N^2)$ | $O(N)$ |
($N$ = 컴퓨터의 수 n. 인접 행렬을 정점마다 한 줄씩 훑으므로 탐색·순회가 $O(N^2)$이고, Union-Find의 union 호출당 비용은 경로 압축으로 상수에 가깝다)
3. 코드
풀이: BFS [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| import java.util.*;
class Solution {
public int solution(int n, int[][] computers) {
boolean[] vis = new boolean[n];
int cnt = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
bfs(i, n, computers, vis);
cnt++;
}
return cnt;
}
static void bfs(int start, int n, int[][] computers, boolean[] vis) {
Queue<Integer> q = new ArrayDeque<>();
q.offer(start);
vis[start] = true;
while (!q.isEmpty()) {
int cur = q.poll();
for (int nxt = 0; nxt < n; nxt++) {
if (computers[cur][nxt] == 0 || vis[nxt]) continue;
q.offer(nxt);
vis[nxt] = true;
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 200;
bool vis[MAXN];
void bfs(int start, int n, vector<vector<int>>& computers) {
queue<int> q;
q.push(start);
vis[start] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int nxt = 0; nxt < n; nxt++) {
if (computers[cur][nxt] == 0 || vis[nxt]) continue;
q.push(nxt);
vis[nxt] = true;
}
}
}
int solution(int n, vector<vector<int>> computers) {
int cnt = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
bfs(i, n, computers);
cnt++;
}
return cnt;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| from collections import deque
def solution(n, computers):
vis = [False] * n
def bfs(start):
q = deque([start])
vis[start] = True
while q:
cur = q.popleft()
for nxt in range(n):
if computers[cur][nxt] == 0 or vis[nxt]:
continue
q.append(nxt)
vis[nxt] = True
cnt = 0
for i in range(n):
if vis[i]:
continue
bfs(i)
cnt += 1
return cnt
|
풀이 2: DFS [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int solution(int n, int[][] computers) {
boolean[] vis = new boolean[n];
int cnt = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
dfs(i, n, computers, vis);
cnt++;
}
return cnt;
}
static void dfs(int cur, int n, int[][] computers, boolean[] vis) {
vis[cur] = true;
for (int nxt = 0; nxt < n; nxt++) {
if (computers[cur][nxt] == 0 || vis[nxt]) continue;
dfs(nxt, n, computers, vis);
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 200;
bool vis[MAXN];
void dfs(int cur, int n, vector<vector<int>>& computers) {
vis[cur] = true;
for (int nxt = 0; nxt < n; nxt++) {
if (computers[cur][nxt] == 0 || vis[nxt]) continue;
dfs(nxt, n, computers);
}
}
int solution(int n, vector<vector<int>> computers) {
int cnt = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
dfs(i, n, computers);
cnt++;
}
return cnt;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| import sys
sys.setrecursionlimit(10**6)
def solution(n, computers):
vis = [False] * n
def dfs(cur):
vis[cur] = True
for nxt in range(n):
if computers[cur][nxt] == 0 or vis[nxt]:
continue
dfs(nxt)
cnt = 0
for i in range(n):
if vis[i]:
continue
dfs(i)
cnt += 1
return cnt
|
풀이 3: Union-Find [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
static int[] p;
static int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
static boolean union(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
p[x] = y;
return true;
}
public int solution(int n, int[][] computers) {
p = new int[n];
for (int i = 0; i < n; i++) {
p[i] = i;
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (computers[i][j] == 1) union(i, j);
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (i == p[i]) cnt++;
}
return cnt;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 200;
int p[MAXN];
int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
p[x] = y;
return true;
}
int solution(int n, vector<vector<int>> computers) {
iota(p, p + n, 0);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (computers[i][j]) unite(i, j);
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (i == p[i]) cnt++;
}
return cnt;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| def solution(n, computers):
p = list(range(n))
def find(x):
while x != p[x]:
p[x] = p[p[x]]
x = p[x]
return x
def union(x, y):
x, y = find(x), find(y)
if x == y:
return False
p[x] = y
return True
for i in range(n):
for j in range(i + 1, n):
if computers[i][j]:
union(i, j)
return sum(i == p[i] for i in range(n))
|