[Python 알고리즘] 파핑파핑 지뢰찾기 - SWEA

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc

---

문제 분석

지뢰찾기 형태의 2차원 배열.

지뢰가 아닌 곳을 모두 오픈하기 위한 최소 클릭 수를 구하라.

단, 주변의 지뢰 개수가 0인 곳을 클릭하면 주변 위치까지 연쇄적으로 오픈된다.

 

접근

DFS 혹은 BFS가 적절하다.

최소 값을 구하는 문제이므로 BFS로 진행하자.

 

최소가 되게 하는 클릭 수를 구하는 것이 까다롭다.

그러나 몇 가지 케이스를 상상하다보면 다음을 알 수 있다.

• 값이 0인 곳들이 인접한 경우, 아무거나 클릭해도 모두가 연쇄적으로 클릭된다.
• 0인 곳을 모두 클릭하고 나면, 나머지 원소는 모두 일일이 클릭해야 한다.

 

첫 번째 탐색 

• 행렬의 모든 원소에 인접 지뢰 개수 표시 

두 번째 탐색 

• 값이 0인 원소는 주변을 방문 처리
• 방문 처리 중에 만나는 값이 0인 원소는 q에 삽입 후 탐색
• 그렇지 않은 원소는 방문 처리만 

세 번째 탐색 

• 남은 .의 개수 세기

 

코드

from collections import deque

dx = [1, 1, -1, -1, 1, -1, 0, 0]
dy = [1, -1, 1, -1, 0, 0, 1, -1]

def openMatrix(x, y):
    tmp = 0
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            continue
        if matrix[nx][ny] == "*":
            tmp += 1
    
    matrix[x][y] = tmp


def clickZeroElement(a, b):

    q = deque()
    q.append([a, b])
    matrix[a][b] = "*"

    while q:
        x, y = q.popleft()

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            if matrix[nx][ny] == 0:
                q.append([nx, ny])
                matrix[nx][ny] = "*"
            
            elif matrix[nx][ny] != "*":
                matrix[nx][ny] = "*"

testCase = int(input())

for tc in range(testCase):
    n = int(input())
    matrix = [list(input()) for _ in range(n)]
    total = 0

    for i in range(n):
        for j in range(n):
            if matrix[i][j] == ".":
                openMatrix(i, j)
    
    for i in range(n):
        for j in range(n):
            if matrix[i][j] == 0:
                clickZeroElement(i, j)
                total += 1
    
    for i in range(n):
        for j in range(n):
            if matrix[i][j] != "*":
                total += 1
    
    print(f"#{tc + 1} {total}")

 

 

전형적인 삼성 스타일의 문제인 듯하다.

그래도 아주 어렵지는 않다.

 

클릭 수가 최소가 되게 하는 방법을 고민하다보면, 완전 탐색으로는 불가능하다는 것을 알게 된다.

그 상태에서 문제의 조건에 집중하면 풀이에 접근할 수 있게 된다.

 

직관적으로도 지뢰찾기 게임을 할 때 0부터 클릭하지 않는가.

---

참고

https://heo-it-til.tistory.com/entry/SWEA-D4-%ED%8C%8C%ED%95%91%ED%8C%8C%ED%95%91-%EC%A7%80%EB%A2%B0%EC%B0%BE%EA%B8%B01868-Python