조상을 조회할 때 find를 사용하고 합집합을 할 때 유니온을 하는데 유니온을 할 때 본인의 최고 조상이 제대로 조회되는지 확인해야합니다.
import sys
sys.setrecursionlimit(500000000)
n, m = map(int, sys.stdin.readline().split())
check = [i for i in range(n + 1)]
def find(k):
if check[k] != k:
check[k] = find(check[k])
return check[k]
2번 째와 3번 째 코드 박스를 비교하면 2번 째는 find를 통해서 조상을 비교하고 3번 째는 check 리스트를 통해 조상을 비교합니다. check에 본인의 조상이 들어가는 것은 맞지만 그게 최고 조상인지 아닌지 확인할 필요가 있습니다.
간단한 반례를 보면
5 6
0 5 4
0 4 2
0 2 0
0 5 3
0 3 1
1 0 1
일 때 최종 check는 [0, 1, 0, 1, 3, 4]가 나옵니다. 한 번 그려서 살펴보면 바로 이해가 갈 것입니다. 체크를 통해 조상을 확인하고 그 조상의 체크를 조회하면 최고 조상이라고 생각했지만, 여러 번 이어진 노드가 있다면 그것은 단지 2개 위의 조상이지 최고 조상이 아닙니다. 유니온 파인드 문제에서 최고 조상을 찾아야 한다면 무조건 find를 사용하는 것을 기억합시다.
yoon6624 4년 전 4
유니온 파인드 문제에서 조상을 찾아 비교하는 것이 중요한 로직입니다.
조상을 조회할 때 find를 사용하고 합집합을 할 때 유니온을 하는데 유니온을 할 때 본인의 최고 조상이 제대로 조회되는지 확인해야합니다.
import sys sys.setrecursionlimit(500000000) n, m = map(int, sys.stdin.readline().split()) check = [i for i in range(n + 1)] def find(k): if check[k] != k: check[k] = find(check[k]) return check[k]if find(a) > find(b): check[check[a]] = check[b] elif check[b] > check[a]: check[check[b]] = check[a]if check[a] > check[b]: check[check[a]] = check[b] elif check[b] > check[a]: check[check[b]] = check[a]2번 째와 3번 째 코드 박스를 비교하면 2번 째는 find를 통해서 조상을 비교하고 3번 째는 check 리스트를 통해 조상을 비교합니다. check에 본인의 조상이 들어가는 것은 맞지만 그게 최고 조상인지 아닌지 확인할 필요가 있습니다.
간단한 반례를 보면
일 때 최종 check는 [0, 1, 0, 1, 3, 4]가 나옵니다. 한 번 그려서 살펴보면 바로 이해가 갈 것입니다. 체크를 통해 조상을 확인하고 그 조상의 체크를 조회하면 최고 조상이라고 생각했지만, 여러 번 이어진 노드가 있다면 그것은 단지 2개 위의 조상이지 최고 조상이 아닙니다. 유니온 파인드 문제에서 최고 조상을 찾아야 한다면 무조건 find를 사용하는 것을 기억합시다.