퍼콜레이션(격자 침투) 계산기

격자의 칸이 확률 p로 «열림»일 때 열린 칸끼리 이어져 위에서 아래로 길이 나는지를 보는 모형입니다. 커피 가루 사이로 물이 내려가는 것, 암반에 지하수가 흐르는 것, 산불이 번지는 것, 전염병이 퍼지는 것이 모두 같은 꼴이라 물리학·재료공학·역학에서 널리 쓰입니다.

p를 조금씩 올리면 뚫릴 확률이 완만히 오르지 않고 어느 지점에서 갑자기 섭니다. 그 자리가 문턱값입니다. 2차원 정사각 격자의 사이트 퍼콜레이션에서는 0.5927 언저리로 알려져 있습니다. 물이 0℃에서 어는 것과 같은 «상전이»가 이 단순한 확률 모형에서 나옵니다.

닫힌 식이 알려져 있지 않아 수치 실험으로 얻은 값입니다. 그래서 이 계산기는 그 값을 상수로 쓰지 않고 매번 시뮬레이션으로 추정합니다. 칸을 무작위 순서로 하나씩 열다가 처음 뚫리는 순간의 «열린 칸 비율»을 재는 방식이며, 한 번 돌 때마다 문턱값 하나가 나오므로 평균과 95% 신뢰구간을 바로 얻습니다.

뚫릴 확률 곡선이 가팔라집니다. 문턱값의 평균은 작은 격자에서도 이미 0.59 언저리지만, 실험 간 흩어짐(표준편차)이 크게 줄어듭니다. 무한히 큰 격자에서는 문턱 아래에서는 절대 안 뚫리고 위에서는 반드시 뚫리는 계단이 됩니다.

칸을 열 때마다 이웃한 열린 칸과 묶습니다. 맨 위에 가상의 위쪽 칸, 맨 아래에 가상의 아래쪽 칸을 두면 «뚫렸는가»는 그 둘이 같은 덩어리인지 한 번 물어보면 끝납니다. 경로 압축과 크기 기준 합치기를 쓰면 사실상 상수 시간에 답합니다.

가상의 아래쪽 칸까지 한 자료구조에 넣으면, 뚫린 뒤에는 아래쪽에 매달린 막다른 칸들까지 위와 이어진 것으로 보이는 문제입니다. 아래에서 위로 거슬러 올라간 셈이라 물이 찬 칸을 칠할 때 틀린 그림이 나옵니다. 이 계산기는 자료구조를 둘 두어 피합니다 — 뚫림 판정용(위·아래 모두)과 물이 찬 칸 표시용(위쪽만)입니다.

같은 격자를 BFS로 다시 판정해 봅니다. 유니온–파인드는 칸을 묶어 가며 판정하고 BFS는 다 만들어 놓은 격자를 훑으므로 같은 실수를 저지를 길이 없습니다. 이 계산기는 두 판정 결과를 화면에 나란히 냅니다.

아닙니다. 위·아래·좌우로 맞닿은 것만 이어진 것으로 봅니다. 대각선까지 세면 문턱값이 크게 달라집니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.