[알고리즘2] Ch2. Union Find 실습 - Percolate

• 문제 설명
  n*n개의 객체
  각 객체는 열림/닫힘 중 하나의 상태
  가장 윗 줄이 가장 아랫 줄에 연결되었다면 percolate
  p: 열린 격자의 비율(%) (평균적으로 p값이 얼마 이상일 때 항상 percolate하는가?)

• 구현 방법

1. n*n개의 객체 닫힌 상태로 초기화

2. 닫힌 객체 중 하나를 임의로 선정, 열린 상태로 바꾸고 percolate하는지 확인 (이 단계를 percolate할 때까지 반복)
   -인접한 두 객체가 모두 열린 상태라면 서로 union되어 같은 connected component에 속한다고 간주
   -한 객체 열 때마다 인접한 네 곳(위,아래,왼,오)이 열렸는지 확인해 열린객체와 모두 연결
   -윗줄 n개 객체와 모두 연결된 가상의 객체 추가, 아랫줄 n개 객체와 모두 연결된 가상의 객체 추가 (처음부터 union하지 말고, 윗줄 n개와 아랫줄 n개 중 열린 객체가 생기면 union)
   -추가한 2개의 가상의 객체가 서로 연결된다면 percolate하는 것

3. percolate할 때 열려있는 객체의 비율 (열린 객체 수 / n*n)을 p의 예측치로 사용
   -열린객체 수에 가상의 객체 2개는 포함되지 않도록 유의
   ex) 25개 중 9개가 열려있다면 9/25 = 0.36

4. 위의 시뮬레이션 여러 번 반복해 p의 평균과 표준편차 구하기
   -평균: statistics.mean()
   -표준편차: statistics.stdev()
   -소수점 아래 절삭 x
   -"return 평균, 표준편차"

• Python 코드

# simulate 함수 정의. 매개변수로 격자의 크기(n)과 시뮬레이션 반복 횟수(t)를 받음.
def simulate(n, t):
	# root 함수 정의. 인덱스 i가 속한 집합의 루트를 찾아 반환
    def root(i):
        while i != ids[i]:
            ids[i] = ids[ids[i]]
            i = ids[i]
        return i

	# connected 함수 정의. 두 인덱스 p, q가 같은 집합에 속하는지 확인하고 T/F값 반환.
    def connected(p, q):
        return root(p) == root(q)

	# union 함수 정의. 두 인덱스 p, q가 속한 집합을 합치며, 작은 집합을 큰 집합에 합침.
    def union(p, q):
        id1, id2 = root(p), root(q)
        if id1 == id2:
            return
        if size[id1] <= size[id2]:
            ids[id1] = id2
            size[id2] += size[id1]
        else:
            ids[id2] = id1
            size[id1] += size[id2]

    number = []
    first = n * n # 맨 윗줄과 연결된 가상의 객체
    last = n * n + 1 # 맨 아랫줄과 연결된 가상의 객체
	for c in range(t): # 주어진 횟수(t)만큼 시뮬레이션 반복하는 for문
        cnt = 0 # 열린 객체의 수
        idx = []
        ids, size, oc = [], [], []
        for i in range(n*n):
            idx.append(i)
        random.shuffle(idx)

        for i in range(n*n+2):
            ids.append(i) # index 0~26 객체 추가
            size.append(1) # 객체 추가할 때마다 사이즈 1씩 늘림
            oc.append(0) # 모두 닫힌 상태로 초기화

        while True:
            a = idx.pop() #임의로 선택된 인덱스 a
            # 맨 왼쪽 가장자리 줄이 아니고, 인덱스 a 왼쪽이 열린 상태라면,
            if a % n != 0 and oc[a - 1] == 1:
                union(a, a - 1) # 인덱스 a와 인덱스 a 왼쪽 결합
            # 맨 오른쪽 가장자리 줄이 아니고, 인덱스 a 오른쪽이 열린 상태라면,
            if (a + 1) % n != 0 and oc[a + 1] == 1:
                union(a, a + 1) # 인덱스 a와 인덱스 a 오른쪽 결합
            # 맨 윗 줄이 아니고, 인덱스 a 위쪽이 열린 상태라면,
            if a - n >= 0 and oc[a - n] == 1:
                union(a, a - n) # 인덱스 a와 인덱스 a 위쪽 결합
            # 맨 아랫 줄이 아니고, 인덱스 a 아래쪽이 열린 상태라면,
            if a + n < n * n and oc[a + n] == 1:
                union(a, a + n) # 인덱스 a와 인덱스 a 아래쪽 결합

            oc[a] = 1 # 현재 위치 a를 열린 상태로 변경
            cnt += 1 # 열린 객체의 수 1 증가
            if 0 <= a < n: # a가 맨 윗줄 객체라면,
                union(first, a) # 가상의 객체 first와 a 결합
            if n * n - n <= a < n * n: # a가 맨 아랫줄 객체라면,
                union(last, a) # 가상의 객체 last와 a 결합

            if connected(first, last): # 객체 first와 last가 같은 집합에 속한다면
                number.append(cnt / (n * n)) # number 리스트에 열린 상태의 객체 비율 저장 
                break

    mean = statistics.mean(number) # 열린 객체 비율 계산 t번 실행한 결과의 평균
    stdev = statistics.stdev(number) # 열린 객체 비율 계산 t번 실행한 결과의 표준편차
    return mean, stdev #평균, 표준편차 반환