12/9 풀이

Graph Valid Tree

https://neetcode.io/problems/valid-tree

NeetCode

해당 무방향 그래프가 올바른 트리 형태인지 판단하는 문제였다.
올바른 트리이기 위한 조건은

1. 간선의 갯수가 노드 - 1개일 것.
2. 모든 노드가 서로 연결되어 있을 것
3. 사이클 x

무방향 그래프인 경우에 유니온 파인드를 사용해서 두 노드가 같은 집합에 속하는지 판단하고, 같은 집합에 속하는 경우 사이클이 있다고 판단하여 트리 조건에 부합하지 않도록 구현했다. 방향이 있는 그래프에선 위상 정렬을 사용하여 사이클 여부를 판단했지만, 위상 정렬은 무방향 그래프에선 잘 사용하지 않는다고 한다.

Number of Connected Components in an Undirected Graph

https://neetcode.io/problems/count-connected-components

NeetCode

원소들이 같은 집합일 때, 1씩 더해주는 문제로 마찬가지로 유니온 파인드를 사용해서 풀어주었다.

HashSet을 사용하여 부모 노드값들을 넣어주었고, 최종적으로 set의 사이즈를 리턴해줘서 풀었다. 
처음엔 parent[i] 값들을 set에 넣어주었는데, 그런 경우 문제가 발생했었다.

이런 형태인 경우

4 6
5 4
6 6
7 6

 

모두 같은 집합에 속하는데, parent[i]의 값들을 출력하는 경우 (5,4) 값이 다르기 때문에 코드 상으론 집합이 두개로 나뉜다. 

따라서, find 메서드를 통해서 재귀적으로 부모를 찾아야 모두 같은 집합임을 확인할 수 있다.

4 6
5 6
6 6
7 6

 

(5의 부모 노드가 6임을 확인 가능)

무방향 그래프인 경우 위상 정렬을 통해 사이클 존재를 판단하고, 방향 그래프인 경우 유니온 파인드를 통해 문제를 접근해야겠다. Or 간단하게 dfs, bfs로 풀이