2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
문제 조건 파악 및 접근
컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.
컴퓨터는 100 이하는 갖지만 최대 간선 수는(n*(n-1)) / 2 이므로 4,950개까지 가능.
그래프 문제고 DFS, BFS을 활용하면 된다.
결국 1에 연결된 노드의 개수를 파악하라는게 문제의 최종적인 질문.
풀이 1. BFS
풀이 2. union-find를 활용
union으로 "동일 집합"을 구성하고 마지막에 1에 연결된 노드 개수만 세주면 되겠다는 생각을 갖게됨.
소스 코드
Union-Find
|
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
import java.io.*;
import java.util.*;
public class _2606_바이러스 {
static int[] computers;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine()); // 컴퓨터 개수
computers = new int[N + 1];
for (int i = 1; i < N + 1; i++) {
computers[i] = i;
}
int answer = -1;
int linkCnt = Integer.parseInt(br.readLine());
for (int i = 0; i < linkCnt; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
union(from, to);
}
for (int i = 1; i < N + 1; i++) {
System.out.println(i + " -> " + find(i));
if(find(i) == 1){
answer++;
}
}
System.out.println(answer);
bw.flush();
br.close();
bw.close();
}
public static void union(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return;
}
if (x < y) {
computers[y] = x;
} else {
computers[x] = y;
}
}
public static int find(int x) {
if (computers[x] == x) {
return x;
}
return computers[x] = find(computers[x]);
}
}
|
cs |
Union-Find 복습 및 피드백
Union-Find는 다음을 수행한다.
- Union(a, b)를 수행하면 a가 속한 집합과 b가 속한 집합을 합친다.
- Find(a)는 a가 속한 집합의 '대표'를 반환한다. 즉, Find(a) == Find(b)라는 것은 두 집합의 대표가 동일하다는 의미이므로, a와 b가 동일한 집합에 속해있다는 것과 동치다.
1) 문제에서 주어진 네트워크는 트리가 아니다.
그러니 "5번 노드처럼 저렇게 한개의 노드가 부모를 두개를 갖는 경우에도" 같은 표현은 올바르지 않다. 5번 노드는 1번, 2번 노드와 연결되었을 뿐, 부모를 가지지 않는다.
2) Union-Find는 독립적인 트리의 집합을 만드는 것이다. 이 트리 상에서 5번 노드의 부모는 parent[5]에 해당하므로 당연히 하나다.
3) Union-Find로 구현된 위 코드의 목적, 즉 '집합을 합치는 것'과 '동일 집합에 속해있는지 판별하는 것'을 잘 수행한다는 것을 믿으면, parent[5]가 1인지, 2인지, 아니면 아예 다른 값인지는 중요하지 않다. 중요한 건 5번 노드와 1번 노드가 동일한 연결 요소에 속했으므로 Find(5) == Find(1)일 것이라는 사실이다.
BFS
|
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
import java.io.*;
import java.util.*;
public class _2606_바이러스_graph {
static int[][] graph;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine()); // 컴퓨터 개수
graph = new int[N + 1][N + 1];
visited = new boolean[N + 1];
int linkCnt = Integer.parseInt(br.readLine());
for (int i = 0; i < linkCnt; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
graph[from][to] = 1;
graph[to][from] = 1;
}
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
visited[1] = true;
int count = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int i = 1; i < graph.length; i++) {
if (graph[cur][i] == 1 && !visited[i]) {
visited[i] = true;
queue.offer(i);
count++;
}
}
}
System.out.println(count);
bw.flush();
br.close();
bw.close();
}
}
|
cs |