목록네트워크 (1)

소근소근

[프로그래머스 - 네트워크] BFS, 분리집합(disjoint set) Union & Find C++

BFS/DFS 분류에 있는 문제였지만, 분리집합으로 풀었다. 컴퓨터 두대가 연결 되면 같은 네트워크(같은 집합)으로 분류되기 때문이다. 연결된 컴퓨터 두대는 union해서 같은 집합으로 보고, 마지막에 집합의 개수를 출력하면 된다. #include #include #include #include #include using namespace std; int parent[200]; map m; int Find(int x){ if(x==parent[x]) return x; return parent[x] = Find(parent[x]); } void Union(int x, int y){ int px = Find(x); int py = Find(y); if(px != py){ parent[px] = py; } }..
Algorithm 2022. 1. 8. 18:24
이전 Prev 1 Next 다음