지뢰가 있는 지점과 없는 지점을 포함한 지도가 주어지며 한 지점을 클릭할 시 두 가지 이벤트가 발생한다.
- 지점 주변에 지뢰가 있는 경우:
해당 지점 주변의 지뢰 수가 해당 좌표에 할당된다.- 지점 주변에 지뢰가 없는 경우:
해당 지점과 해당 지점 주변의 8방위가 0으로 할당된다.
이때, 지뢰를 제외한 모든 좌표의 숫자를 표시할 수 있는 최소클릭횟수를 구하는 문제
- 처음 문제를 잘못 접근함. (3x3, 3x2, 2x3, 2x2 델타 탐색을 모두 하는 등... 잘못된 방식)
- 먼제 모든 좌표를 탐색하며 해당 좌표 주위의 지뢰 수를 지도에 할당해야 함
- 주변 지뢰 수가 0인 지점에서 방문체크를 하며 BFS를 돌려야 함
from collections import deque
# 기준 좌표를 감싸고 있는 8개의 좌표(3x3 모양)를 델타 검색 할 것임
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
# 주위에 지뢰가 없는 좌표가 연결되어 있으면 연쇄적으로 탐색하기 위한 너비우선 탐색
def bfs(index):
queue = deque() # 큐 생성
queue.append(index)
while queue: # 큐가 빌 때 까지 반복
r, c = queue.popleft() # 큐 맨 앞의 좌표를 꺼내 해당 좌표를 기준으로 8방으로 탐색
for i in range(8): # 8방으로 탐색
dr, dc = r + dx[i], c + dy[i] # 탐색할 지점의 좌표 dr, dc
if 0 <= dr < N and 0 <= dc < N and V[dr][dc] == False: # 이전에 방문한 적이 없던 좌표이고 지도 내의 범위에 있는 좌표면
V[dr][dc] = True # 해당 좌표를 방문 체크함
if M[dr][dc] == 0: # 이 좌표가 주위에 지뢰도 없는 좌표라면
queue.append((dr, dc)) # 큐에 추가
# 한 지점 주위에 지뢰가 몇개나 있는지 반환하는 함수
def get_mine(index):
r, c = index
mine = 0
for i in range(8):
dr, dc = r + dx[i], c + dy[i]
if 0 <= dr < N and 0 <= dc < N and M[dr][dc] == '*':
mine += 1
return mine
for T in range(1, int(input())+1):
N = int(input()) # 지도의 크기
M = [list(input()) for _ in range(N)] # 지도를 담을 이중 리스트
safe_zone = [] # 주위에 지뢰가 없는 좌표를 담을 함수
ans = 0 # 지뢰를 피해가기 위한 최소 클릭 횟수
for i in range(N):
for j in range(N):
if M[i][j] == '.': # 이 작업을 지뢰 기준으로 처리하면 더 빠른 결과를 얻을 수 있음
M[i][j] = get_mine((i, j)) # 모든 좌표를 순회하면서 지뢰가 아닌 지점 주위의 지뢰 수를 찾고 해당 값을 좌표에 할당한다
if M[i][j] == 0:
safe_zone.append((i, j)) # 주위에 지뢰가 없는 좌표라면 safe_zone 리스트에 추가한다
V = [[False for _ in range(N)] for _ in range(N)] # 방문 체크 리스트
# 주위에 지뢰가 없었던 좌표들을 가져와 해당 좌표를 기준으로 8방으로 탐색을 한다.
# 탐색한 좌표의 주위에도 지뢰가 없다면 탐색 좌표를 기준으로 연쇄적으로 탐색을 한다.
for i in safe_zone:
r, c = i
if V[r][c]: # 너비우선 탐색을 하며 이미 방문했던 좌표라면 건너 뛴다.
continue
V[r][c] = True # 해당좌표를 탐색했다는 방문체크
bfs(i) # 연쇄적으로 탐색을 하기위해 너비우선 탐색을 함
ans += 1 # 클릭 수 + 1
for i in range(N):
for j in range(N):
if V[i][j] == False and M[i][j] != '*': # 지뢰가 있는 좌표도 아니고 BFS로 연쇄 탐색을 한 지점도 아니라면
ans += 1 # 클릭 수 + 1
print('#{} {}'.format(T, ans))