동치관계(Equivalence Relation) - DFS(Stack) & Matrix

동치관계란?

동치관계란 모든 원소 사이에서 동치율이 성립하는 것을 말한다. 동치관계가 성립하기 위해서는 반사, 대칭, 추이를 만족해야한다.

 

동치관계를 코딩으로 알기 위해서는?

 

위의 동치관계가 Minimul Form으로 주어진다고 하자. Minimul Form이란 유추가 가능한 쌍들은 주어지지 않는 것을 말한다.

ex)

10 7 -> 총 10개의 node 7개의 input

 1 3

 3 9

 6 2

 5 10

 7 3

 4 9

 8 10

 

동치관계를 위해서는 Marker와 Matrix가 필요하다. 추가로 Stack도 필요하다.

위 - Marker 아래 - Matrix

Marker은 방문한 Node를 체크하는 역할을 하고 Matrix는 Node간의 연결 관계를 담고있다.

1. 가장 먼저 1번 Node에서 시작한다.(어떤 Node에서 시작하느냐는 상관 없다.)

2. Marker에서 1번 Node를 1로 표시한다.

3. Matrix에서 1번 Node가 갈수있는 다음 노드로 이동한다 (위의 경우 3번 Node) 1번 Node를 Stack에 넣는다

4. 3번 Node를 마킹하고 3번 Node가 갈수 있는 다음 노드로 이동한다

5. 위 DFS 과정을 반복하고 Stack이 empty면 Marker로 돌아와서 마킹이 안돼있는 노드로 이동한다.

 

* 위 알고리즘만을 돌리면 marker는 계속 처음부터 search하므로 $O(n^2)$ 시간이 소요되고 Matrix도 한 Column에서만 $O(n^2)$이 소요된다 이를 줄이기 위해 이미 Search한 Marker와 Matrix를 기억하는 변수를 두면 O(n)으로 줄일 수 있다.

 

그러나 위 알고리즘은 Matrix전체를 보면 Marker와 Matrix를 기억하는 변수가 있더라도 전체를 보면 $O(n^2)$ 시간이 소요된다. Matrix를 보면 0이 들어가있는 공간이 쓸데없이 많기 때문이다. 0의 공간을 없애기 위해 Linked List와 C++에서는 vector, Python에서는 list를 이용 할 수 있다.