uniofind (1) 썸네일형 리스트형 유니온 파인드 : JAVA 정의 어떤 그래프에서 서로 인접한 그래프가 있을때 특정 노드 u와 v가 서로 같은 그래프에 있는가를 판별할 때 사용하는 방법이다. graph[i][j] = 1 이라는 것은 서로 연결되어 있다는 뜻이다. 만약 서로 연결되어 있다면 Union 두개의 노드를 같은 집합으로 합친다는 뜻이다. 이때 Find(i) Find(x) 를 하게 되는데 Find는 가장 위에 있는 부모의 값을 리턴하고 재귀과정에서 연결되 Node를 부모 노드에 바로 붙여준다. 이렇게 되면 처음 parent값은 한다리를 거쳐간다는것인데 이렇게되면 parent[x]의 값은 x가속한 집합이라고는 할수 없다. 하지만 각각에대해 Find를 돌리면 find가 재귀적으로 가장 부모노드에 연결시켜주므로 값이 제대로 나오는 것을 확인 할 수 있다. 소스코드.. 이전 1 다음