예전에 너무 좋아했던 그래프 문제. 그러나 오랜만에 풀어볼려니깐 많이 헷갈렸고 어떻게 시작해야할지도 까먹어서 다른 사람의 코드 답을 보다보니 점점 생각이 났고 나만의 코드로 쓰는게 가능해졌다. 문제의 내용은 직접적으로 이어진 그래프 포인트가 있고 그렇지 않은 포인트가 있는데 이어져있는 포인트는 하나의 숫자로 세면 되고 이어지지 않은 포인트는 또 따로 기록하여 총 갯수를 구하면 되는 문제이다.
가장 첫번째로 접근했던 dfs 방식..visited 벡터를 유지하면서 만약에 하나의 포인트가 방문이 되지 않았다면 그 포인트에 연결된 모든 포인트를 탐색함으로써 벡터를 업데이트해주고 answer 을 증가시키는 과정에서 자연스럽게 이미 방문된 포인트는 배제되서 맞는답이 나온다. 제일 직접적이고 깔끔한 답이라 생각하지만 union find 방식으로도 문제를 접근해보니 더욱 자신감이 생겼다.
두번째로 접근한 Union Find 방식. visited 라는 벡터를 안쓰고 첫번째로 모든 포인트들의 조상을 자기 자신으로 설정해주었다. 그리고 isConnected 벡터를 탐색하는 과정에서 만약 포인트가 다른 포인트와 여결이 되었다 하면은 둘의 조상이 같은지를 findParent 함수로 확인을 하고 다르다고 하면 둘의 조상 관계를 업데이트 시켜줬다. 이런 과정에서 둘이 이어진 순간 answer 하나가 줄어든 관계로 루프를 이어가다보면 마지막에는 답이 나오게 된다.
배운점:
1. dfs 나 bfs를 할때는 꼭 visited 벡터를 잘활용하자.
2. union find 를 사용할때 제일 중요한건 조상을 자기 자신으로 맞추고 탐색을 시작하는거 같다. 문제를 잘 읽고 실수하지 말자.
