구름톤 챌린지 2주 차 학습 일기(Day 02)

문제

 

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

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

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

 

 

예제 설명

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

 

 

 

 

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

 

 

 

 

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

 

 

 

 

코드

from sys import stdin as s
from collections import deque

def bfs(K):
	global cnt 
	
	while q:
		ci, cj = q.popleft()
		count = 0
		
		dx = [0,1,0,-1,-1,1,1,-1]
		dy = [1,0,-1,0,-1,-1,1,1]
		
		for i in range(8):
			nx = dx[i] + ci
			ny = dy[i] + cj 
			
			if 0<=nx<N and 0<=ny<N and goorm[nx][ny]==1:
				count+=1 
		
		if count == K:
			cnt += 1
	return cnt

if __name__=='__main__':
	N,K = map(int,s.readline().split())
	goorm = [list(map(int,s.readline().split())) for _ in range(N)]
	q = deque()
	ans = deque()
	cnt = 0 
	for i in range(N):
		for j in range(N):
			if goorm[i][j] == 0:
				q.append((i,j))

	result = bfs(K)

	
	print(result)

 

 

 

 

느낀점

이 문제는 한 점을 기준으로 주위 8칸을 탐색을 했을 때 1의 개수를 찾는 문제입니다. 저는 이 문제를 풀기 위해서 BFS를 활용하여 처음에 0의 좌표를 다 찾아서 큐에 넣었습니다. 그리고 그 큐를 pop 하면서 dx, dy를 설정해서 8칸을 탐색을 하였고 1의 개수를 파악을 합니다.

이때 처음에는 1의 개수를 파악해서 해당 i, j좌표 값을 바로 count 된 숫자로 바꿨더니 정확한 개수 측정이 불가능했습니다. 따라서 이 문제는 모든 탐색을 끝날 때까지 count개수를 처음 좌표에 반영하면 안 되고 따로 return을 받아서 넘겨주는 방법과 전체 탐색이 다 끝나고 난 후에 한 번에 업데이트를 해주는 방법이 있습니다.