지뢰찾기

풀이

 이 문제는 그리디 + 구현 문제다. 테두리 옆의 '#' 즉 숫자 옆의 '#'들만 신경 쓰면 된다. 그 외의 '#'들은 지뢰가 있을 수도 있고 없을 수도 있지만, 문제에서 요구하는 바가 최대값이기 때문에 지뢰가 있다고 가정한다. 문제 풀이의 핵심은 '#' 주위에 '0'이 없으면 지뢰가 묻혀있다고 가정하고 주변 숫자들을 1씩 감소시키면 된다.

n = int(input())
graph = []
for _ in range(n):
    graph.append(list(input()))

# 12시부터 시계방향
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

count = 0
# '#' 주변 숫자 1씩 감소
def bomb(x, y):
    for i in range(8):
        nx = x+dx[i]
        ny = y+dy[i]
        if graph[nx][ny] != '#' and graph[nx][ny] != 'bomb':
            graph[nx][ny] = str(int(graph[nx][ny])-1)

# '#' 주변에 '0'이 없으면 지뢰 가능
for x in range(n):
    for y in range(n):
        flag = 0
        if graph[x][y] == '#':
            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]
                if graph[nx][ny] =='0':
                    flag = 1
                    break
            if flag == 0:
                bomb(x, y)
                graph[x][y] = 'bomb'
                count += 1

print(count)

시간복잡도 : O(n^2)