멧돼지 사령관의 노하우는 모두 맞지만 그런 방법으로 찾아서 어느 세월에 지뢰를 다 찾는단 말이람. 그래서 나는 멧돼지 사령관이 말한 전략들을 토대로 알고리듬을 만들어서 컴퓨터로 해결해봤어.
내가 만든 알고리듬은 먼저 게임판 정중앙의 칸을 선택해. 그리고 나온 숫자 중에서 1만 3개 있는 2×2 구역 중 빈칸을 찾아 그곳을 지뢰로 표시하지. 맞아, 좀 전에 멧돼지 사령관이 말한 전략 ➍번을 사용한 거야. 그렇게 찾은 지뢰의 위치를 보고 지뢰가 절대 있을 수 없는 곳을 파악하지. 1 주변의 8칸에 이미 지뢰가 하나 있다면 나머지 7칸에는 지뢰가 없다는 사실을 이용하는 거야. 이 정도의 과정만을 사용해 알고리듬을 만들어도 크기가 9×9인 지뢰밭의 지뢰를 모두 찾을 수 있어. 이 알고리듬을 ‘단순 알고리듬’이라고 하지.
하지만 16×16, 16×30으로 지뢰밭의 크기가 점점 늘어나면 단순 알고리듬으로는 해결할 수 없어. 이런 경우엔 ‘탱크 솔버 알고리듬’을 써야 하지. 탱크 솔버 알고리듬은 숫자가 일부 공개된 칸 주변에 지뢰가 어디 있는지 모를 때, 지뢰가 있을 수 있는 모든 경우를 구한 뒤 각 칸에 지뢰가 등장한 횟수를 구해 횟수가 큰 곳부터 지뢰가 있다고 가정하고 지뢰를 찾는 거야.
아래 문제 상황에서 공개된 칸 주변에 지뢰가 분포할 수 있는 경우는 총 11가지야. 아래 ➌의 그림에 표시된 칸은 11가지 중 10번이나 지뢰가 있었으니 실제 지뢰가 있을 확률이 매우 높겠지?
하지만 단순 알고리듬과 탱크 솔버 알고리듬을 사용해 대부분의 지뢰를 찾았다고 해도 몇 칸 남지 않은 마지막 순간엔 절반의 확률에 맡겨야 하는 경우가 있어. 이때 두 알고리듬은 문제를 해결하지 못하고 정지하게 돼.
아니, 크엉! 그럼 알고리듬을 사용하는 것 역시 완벽하지 않단 말이야?
그…, 그렇긴 하지. 완벽한 방법은 일일이 확인해서 지뢰의 위치를 파악하는 방법뿐이야. 지뢰는 밟으면 터지기 때문에 현실적이지 않지만 이 방법이 가장 정확하지. 이렇게 모든 경우를 따져 문제를 푸는 알고리듬을 ‘완전탐색’이라고 해. 예를 들어 3×3칸에서 아무거나 1칸을 고르고, 남은 8칸 중에 또 1칸을 고르고, 남은 7칸 중에 또 한 칸을 고르는 식으로 다 열어보는 거지. 그럼 최대 9!(=9×8×7×6×5×4×3×1)번 따져봐야 지뢰의 위치를 다 알 수 있지.
