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

구름LEVEL

 

문제

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

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

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

예제 설명

아래의 이미지와 같이 주변의 구름의 수를 계산해서 $K$와 동일한 갯수를 가진 경우를 출력하면 됨.

게임판의 탐색 진행 결과(공백은 0인 경우)

입력

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

출력

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

풀이

ways = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
n, k = map(int, input().split())
field = []
count = 0
for _ in range(n):
    field.append(list(map(int, input().split())))
for i in range(n):
    for j in range(n):
        if field[i][j] == 0:
            temp = 0
            for way in ways:
                nx = i + way[0]
                ny = j + way[1]
                if nx < 0 or nx >=n or ny < 0 or ny >=n:
                    continue
                if field[nx][ny] == 1:
                    temp += 1
            if temp == k:
                count += 1
print(count)

해설

1. 각 위치의 주변 8개 영역을 찾아갈 수 있도록 ways라는 리스트 생성
2. 주어진 게임판 전체를 순회하면서 값이 0인 경우 주변 탐색 진행
3. 주변 탐색 결과에 따른 갯수가 $K$와 일치한 경우 count 증가
4. 탐색 종료 이후 count 출력

배열을 완전 탐색으로 순회하면서 주변을 접근하는 것까지만 하면 되는 구현 중에 기초 문제