Min IT's Devlog

풀이 일자: 23.05.19 난이도: [Medium] 분류: [DFS, BFS, Union Find, Graph] 문제 내용 이번 문제는 undirected graph가 주어졌을 때 이 노드들을 A와 B그룹으로 나눌 수 있는지 여부를 리턴하는 문제로 각 A,B 내부의 노드끼리는 연결되어 있지 않아야 한다. A와 B는 연결되어 있어도 상관없다. 문제 해결 흐름 1. 처음에는 Graph문제이고 A와 B그룹으로 나눌 수 있기 때문에 Union-Find를 떠올렸다. → 가능은 하겠지만 좀더 쉬운 방법을 떠올리고자 했다 2. A그룹과 B그룹을 나누고 같은 그룹의 노드들이 서로 인접하면 안되기 때문에 노드를 색칠하는 문제로 생각해도 되겠다는 생각을 할 수 있다. → BFS를 이용하여 각 level별로 같은 색으로 ..

풀이 일자: 23.05.18 난이도: [Medium] 분류: [Graph] 문제 내용 문제의 내용은 0 ~ N-1까지의 노드가 있는 순환이 없는 graph가 주어졌을 때 모든 노드에 접근하는 것이 목표이다. 최소한의 시작점을 사용하여 위와 같은 목표를 달성할 때 그 때의 시작점들의 집합을 리턴하는 것이 목표이다. 문제 해결 흐름 1. 처음에는 Union-Find를 생각해보았지만 그래프가 방향성이 있는 그래프이고 모두 합쳐져 있어서 부적합하다. → Union-Find는 Pass 2. 그래프를 직접 순회해가면서 각 노드가 접근할 수 있는 노드들의 집합을 구하는 것이 어떨까? → 가능은 하지만 시간이 오래 걸릴 것이다. 이는 cycle이 존재할 수 있어 이에 대한 처리가 필요하고 각 시작점에서 접근가능한 노드..