[구름톤 챌린지] 2주차 7일차 구름 찾기 깃발

 

 

문제

---

구름 찾기 게임은 한 변의 길이가 $N$인 격자 모양의 게임판 $M$에서 진행하는 게임이다. 게임판의 일부 칸에는 구름이 숨겨져 있고, 게임판에 숨겨진 모든 구름의 위치를 찾으면 게임에서 승리할 수 있다.

구름 찾기 게임의 제작자인 플레이어는 조금 더 쉽게 구름을 찾을 수 있도록 도와주는 깃발을 게임판 위에 설치하려고 한다. 깃발은 구름이 없는 칸이면서, 상하좌우와 대각선으로 인접한 여덟 칸 중 구름이 하나 이상 있는 칸에만 설치할 수 있다. 이렇게 설치한 깃발에는 인접한 여덟 칸 중 구름이 있는 칸의 개수에 해당하는 값이 적힌다.

플레이어는 깃발을 세울 수 있는 모든 칸에 깃발을 세워두었다. 문득, 플레이어는 깃발 중 값이 $K$인 깃발이 몇 개나 있는지가 궁금해졌다. 여러분이 플레이어를 대신해 값이 $K$인 깃발의 개수를 세어주자.

예제 설명

---

첫 번째 예제에서 주어지는 게임판은 다음과 같다. 편의상 게임판의 $r$번째 행, $c$번째 열에 해당하는 칸을 $M_{r, c}$와 같이 나타낸다고 하자.

 

$M_{3, 2}$는 구름이 없는 칸이면서, 동시에 주변 여덟 칸 중 구름이 있기 때문에 깃발을 설치할 수 있다. 네 개의 구름이 있으므로 깃발의 값은 4가 된다.

 

게임판의 가능한 모든 위치에 깃발을 설치했을 때의 결과는 아래와 같다. 비어있는 칸은 깃발을 설치하지 않은 칸이다.

 

입력

---

첫째 줄에 게임판의 크기 $N$과 찾고 싶은 깃발의 값 $K$가 공백을 두고 주어진다.
다음 $N$개의 줄에는 게임판의 각 칸에 대한 정보가 $N$개의 문자로 공백을 두고 주어진다. $r$번째 줄에서 $c$번째로 주어지는 문자는 $M_{r,c}$칸에 해당하는 정보이다. 0은 그 칸이 비어있음을, 1은 그 칸에 구름이 숨겨져 있음을 의미한다.

 

• $1 \leq N \leq 1 \ 000$
• $1 \leq K \leq 8$
• $N$과 $K$는 모두 정수이다.
• 각 칸의 정보를 나타내는 문자는 0 또는 1 중 하나이다.

출력

---

값이 $K$인 깃발의 개수를 출력한다.

 

---

문제 접근 방식

---

브루트 포스로 모든 칸들을 확인해가며, 각 칸 마다 주위 $8$칸을 보는 방식을 취했다.

 

이때, 칸들을 확인할 때 구름이 없는 칸에만 깃발을 꽃을 수 있으므로, 구름이 없는 $0$일때에만 주위 $8$칸을 탐색해주었다.

 

이때, 주위 $8$칸의 범위 또한 신경 써주면서 탐색을 진행했다.

 

주위 $8$칸에 있는 구름의 개수를 세어서, 이 개수가 만약 $K$와 같으면 우리가 원하는 깃발의 값이 적혀있는 것이라고 판단할 수 있으므로, 이때 답에 $+1$을 해준다.

 

이 과정을 거쳐서 최종적으로 나온 답을 출력해주었다.

 

---

정답 코드

---

# 구름 찾기 깃발
import sys
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
matrix = [list(map(int, input().rstrip().split())) for _ in range(N)]
flag = 0
dr = [-1, -1, -1, 0, 0, 1, 1, 1]
dc = [-1, 0, 1, -1, 1, -1, 0, 1]
for i in range(N):
    for j in range(N):
        if matrix[i][j]:
            continue
        cnt = 0
        for k in range(8):
            ni, nc = i+dr[k], j+dc[k]
            if 0 <= ni < N and 0 <= nc < N and matrix[ni][nc]:
                cnt += 1
        if cnt == K:
            flag += 1
print(flag)

 

---

특별히 배운 점

---

유명한 지뢰찾기류 문제이기 때문에 좀 더 효율적인 구현이 가능했을 수도 있을 것 같다.