SW Expert Academy 1868. 파핑파핑 지뢰찾기

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE

SW Expert Academy

최소 몇 번의 클릭을 해야 지뢰가 없는 모든 칸에 숫자가 표시될 것인지 출력하는 것이 목표였다. 처음에 브루트 포스로 하려고 하니 시간이 너무 걸릴 것 같아서 잠시 생각을 하였다. 내가 생각해낸 방법은 일단 먼저 주위의 8방향에 지뢰가 없는 지점부터 클릭하여 최대한 최소로 많은 점을 숫자 표시하고, 그다음에 나머지 점들을 전체 맵의 격자 개수에서 지뢰와 최소의 클릭으로 드러낸 점을 빼낸 점을 더하는 것으로 최소 클릭 횟수를 구하는 생각을 하게 되었다. 중간에 구현하는데 효율성을 따지려고 하니 생각이 꼬여서 일단 비효율적으로 코딩하고 제출을 했는데 통과하여 조금 당황했다. 

나의 풀이는 아래와 같다.

def click(x, y, map1, test):
    global visit
    global count
    visit[x][y] = test
    n = len(map1)
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, -1, -1, -1, 0, 1, 1, 1]
    if check(x, y, map1):
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if -1 < nx < n and -1 < ny < n and visit[nx][ny] != test:
                count += 1
                visit[nx][ny] = test
                if check(nx, ny, map1):
                    click(nx, ny, map1, test)
    else:
        visit[x][y] = test
        count += 1
 
 
def check(x, y, map1):
    cnt = 0
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, -1, -1, -1, 0, 1, 1, 1]
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if -1 < nx < n and -1 < ny < n and map1[nx][ny] == '*':
            cnt += 1
    if cnt == 0:
        result = True
    else:
        result = False
    return result
 
 
t = int(input())
visit = [[0 for _ in range(300)] for _ in range(300)]
for test in range(1, t + 1):
    push = 0
    count = 0
    mine = 0
    n = int(input())
    map1 = []
    for _ in range(n):
        map1.append(input())
 
    for i in range(n):
        for j in range(n):
            if map1[i][j] == '*':
                mine += 1
            if check(i, j, map1) and visit[i][j] != test and map1[i][j] != '*':
                push += 1
                count += 1
                click(i, j, map1, test)
    extra = n * n - count - mine
    push += extra
    print('#{} {}'.format(test, push))