알고리즘

연결된 정점들의 개수를 구하는 문제.각 연결된 정점들을 집합이라고 생각하고 union-find로 접근하였다.문제는 바로 맞췄지만 생각보다 시간이 많이 걸렸는데.for문 조건문에서 모든 입력을 받을 필요가 없다는 것을 몰랐다.union에서 연결이 되었는지 boolean

DP와 DFS를 사용하면 풀 수 있다는걸 알았지만 너무 오랜만에 봐서 코드 구현이 헷갈렸던 문제.단순 DFS 완전탐색으로 하게 되면 시간초과가 난다.DP를 활용하여 이전에 갔던 곳을 메모이제이션을 통해 빠르게 값을 누적하는 것이 핵심.