이런식으로 서로 간선으로 연결되어있는 정점들의 집합을 하나의 연결 요소라고 한다.
이 주어진 그래프를 토대로 몇개의 연결 요소가 나오는지 구하는 문제이다.
문제에서 주어지는 정점의 개수는 1000개이다. 이를 일반적인 인접행렬로 표현하려면 1000 * 1000의 배열이 필요하므로, 메모리도 아끼고 실행 시간도 줄일 겸 각 정점이 어느 정점과 연결되어있는지 표현하는 인접행렬로 구현하였다.
문제를 풀기 위해서 dfs를 사용하여 순회하지 않았던 연결 요소라면 true를 반환하여 결과값에 1을 더하고, 순회하였던 연결 요소라면 false를 반환하도록 해주었다.
|
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
72
73
74
75
76
77
78
79
80
|
namespace real연습
{
internal class Program
{
static void Main(string[] args)
{
int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int edge = input[0];
int linkes = input[1];
Graph graph = new Graph(edge);
for (int i = 0; i < linkes; i++)
{
int[] link = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
graph.graph[link[0]].Add(link[1]);
graph.graph[link[1]].Add(link[0]);
}
HashSet<int> visited = new HashSet<int>();
int result = 0;
for (int i = 1; i <= edge; i++) // 1번 정점부터 순회 시작
{
if (dfs_search(i, visited, graph) == true) // 순회한적 없다면
{
result += 1; // 결과값 1 증가
}
}
Console.WriteLine(result);
}
static bool dfs_search(int start, HashSet<int> visited, Graph graph)
{
bool result = false;
Stack<int> stack = new Stack<int>();
if (visited.Contains(start) == false) // 방문하지 않았던 정점일때만 실행
{
stack.Push(start); // stack에 순회를 시작하는 값을 미리 넣어둠
while (stack.Count != 0)
{
int current = stack.Pop(); // 스택의 맨 뒤에있는 값을 뽑아 사용
if (visited.Contains(current) == false) // 해당 정점을 방문하지 않았다면
{
visited.Add(current); // 방문처리
}
for (int vertex = graph.graph[current].Count - 1; vertex >= 0 ; vertex--)
{ // 스택을 맨 위의 값부터 뽑아서 쓰기 때문에, 마지막 index부터 첫번쨰 index까지 역순회
if (visited.Contains(graph.graph[current][vertex]) == false)
{
stack.Push(graph.graph[current][vertex]);
}
}
}
result = true;
}
return result;
}
private class Graph=
{
int _size;
public List<int>[] graph;
public Graph(int size)
{
this._size = size;
this.graph = new List<int>[size + 1];
for (int i = 1; i < size + 1; i++)
{
graph[i] = new List<int>();
}
}
}
}
}
|
cs |
'하루 한 접시' 카테고리의 다른 글
| [백준] 2206번: 벽 부수고 이동하기 [C#] (0) | 2024.08.28 |
|---|---|
| [백준] 2606번: 바이러스 [C#] (0) | 2024.06.27 |
| [백준] 2504번 : 괄호의 값 [C#] (0) | 2024.05.23 |
| [백준] 17298번 : 오큰수 [C#] (0) | 2024.05.22 |
| [백준] 6198번 : 옥상 정원 꾸미기 [C#] (0) | 2024.05.22 |
