[SWEA] D4 : 파핑파핑 지뢰찾기(1868) Python

최근에 풀었던 문제 중에 가장 재밌게 푼 문제인 것 같다.

물론 쉽게 푼 문제는 아니었지만, 어떻게 풀지 고민하는 과정과 실제로 그 과정에서 정답이 나오는 게 알고리즘 문제를 푸는 재미인 것 같다.

문제를 간단히 설명하자면, 몇 번의 클릭으로 지뢰가 아닌 곳을 오픈할 수 있는지 횟수에 대한 최솟값을 묻는 문제이다.

파핑파핑 지뢰찾기 문제설명

추가적인 제약사항은 *(지뢰가 아닌 곳)을 클릭했을 때, 인접한 곳에 지뢰가 없다면 인접한 블록까지 공개가 된다. 그림에서 숫자는 인접한 위치의 지뢰 개수인데, 문제에서 묻는 것은 최소 클릭 횟수이기 때문에 구현하지 않았다.

문제를 처음 보고 최소한의 횟수? 'DFS!'를 생각했지만, 게임판의 길이(N) 이 300까지 가능하기 때문에 DFS는 절대 아니라고 생각했다. 그럼 내 지식에서 남은 보기는 그리디와 BFS를 이용해 푸는 것이었는데, 그리디로 풀 자신이 없어 BFS로 접근하면서 풀어보자 생각했다.

최고의 무기인 손 코딩을 하면서 0을 클릭했을 때 퍼져 나가는 것이 BFS 같다는 생각이 들었고, 더 나아가, 모든 점을 숫자로 바꿔놓고 BFS로 0과 인접한 숫자들을 확장해나가면서 센 후, 나머지 숫자의 개수를 세면 답을 구할 수 있다는 생각을 했다.

이를 코드로 구현하면, 

from collections import deque
delta = [[-1,0],[1,0],[0,-1],[0,1],[-1,-1],[-1,1],[1,-1],[1,1]]


def change_bfs(ni,nj): # 지뢰판이 공개된 배열로 바꾸기
    tmp = 0
    for d in delta:
        dx, dy = ni + d[0], nj + d[1]
        if 0<=dx<N and 0<=dy<N and arr[dx][dy] == '*':
            tmp += 1

    arr[ni][nj] = tmp


def count_check(nr,nc): # 0이면 들어가서 주변숫자 다 *로 바꾸기
    Q = deque()
    Q.append([nr,nc])
    arr[nr][nc] = '*'

    while Q:
        ni, nj = Q.popleft()

        for d in delta:
            dx, dy = ni + d[0], nj + d[1]
            if 0<=dx<N and 0<=dy<N:
                if arr[dx][dy] == 0:
                    arr[dx][dy] = '*'
                    Q.append([dx,dy])

                elif arr[dx][dy] != '*':
                    arr[dx][dy] = '*'


T = int(input())+1
for tc in range(1,T):
    N = int(input())
    arr = [list(input()) for _ in range(N)]

    for i in range(N):
        for j in range(N):
            if arr[i][j] == '.':
                change_bfs(i,j)

    cnt = 0
    for i in range(N):
        for j in range(N):
            if arr[i][j] == 0:
                cnt+= 1
                count_check(i,j)

	# 남은 숫자 갯수 세기
    for i in range(N):
        for j in range(N):
            if arr[i][j] != '*':
                cnt += 1
    print(f'#{tc} {cnt}')

이렇게 된다.

처음 문제를 접했을 때는 막막했지만, '이렇게 하면 될 거 같은데?'라는 생각으로 문제를 접근하고 그 생각이 확신으로 바뀌어 코드로 나타날 때 쾌감이 너무 즐거운 것 같다.

매일 한 개 알고리즘 파이팅!