[BOJ] 2140 지뢰찾기

def dfs(bomblist):
    global N,result
    while bomblist:
        x,y = bomblist.pop()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if (nx == 0 or nx == N-1) or (ny == 0 or ny ==N-1):
                if arr[nx][ny] == 0:
                    break
        else:
            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]
                if (nx == 0 or nx == N-1) or (ny == 0 or ny ==N-1):
                    arr[nx][ny] -= 1
            result += 1
    return

            



N = int(input())
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]
arr = [list(input()) for _ in range(N)]
result = 0
if N >4:
    result += (N-4)**2
bomb = []
for x in range(N):
    for y in range(N):
        if x == 1 or x == N-2:
            if arr[x][y] == '#':
                bomb.append((x,y))
            else:
                arr[x][y] = int(arr[x][y])
        elif 1<x<N-2:
            if y == 1 or y == N-2:
                bomb.append((x,y))
            else:
                if arr[x][y] != '#':
                    arr[x][y] = int(arr[x][y])
        else:
            if arr[x][y] != '#':
                arr[x][y] = int(arr[x][y])
dfs(bomb)
print(result)

 

 지뢰찾기를 하는 문제이다. 테두리에만 숫자가 있고, 그 안은 파악되지않는 지뢰구역이 있다.

이 지뢰구역에서 최대로 설치가능한 지뢰의 개수를 구하는 문제이다.

먼저, 테두리에 직접적으로 닿아있는 칸들을 제외한 나머지 칸들은 전부 지뢰가 있다고 가정을 해야, 최대 지뢰를 구할 수 있다.

그리고 두번째로 테두리에 근접해있는 칸들을 기준으로 8칸을 탐색을 해서, 그 안에 0이 있다면, 해당 구역은 지뢰가 존재할수 없는 공간이니 넘어간다.

하지만, 0이 존재하지 않는 경우 지뢰가 존재하는 경우이니, 지뢰의 수를 1개 늘려주고, 해당 구역의 주변 8칸의 숫자를 1씩 줄여준다.

이걸 반복해준다.

 

여기서 쓴 코드적인 부분은 for else 문이다.

for문을 반복하면서, break를 한번도 마주치지 않으면 자동적으로 else문이 실행되는 것이다.

이걸 통해 따로 flag같은 True False 값 같은 분기점이 없이 진행이 가능했다.