[구름톤 챌린지] Day 7 구름 찾기 깃발

문제

---

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

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

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

예제 설명

---

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

 

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

 

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

 

입력

---

첫째 줄에 게임판의 크기 N과 찾고 싶은 깃발의 값 K가 공백을 두고 주어진다.
다음 N개의 줄에는 게임판의 각 칸에 대한 정보가 N개의 문자로 공백을 두고 주어진다. r번째 줄에서 c번째로 주어지는 문자는

칸에 해당하는 정보이다. 0 은 그 칸이 비어있음을, 1 은 그 칸에 구름이 숨겨져 있음을 의미한다.

• 
• 
• 과 는 모두 정수이다.
• 각 칸의 정보를 나타내는 문자는 0 또는 1 중 하나이다.

 

출력

---

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

예시 1

입력

4 2
0001
0010
0010
0111

출력

2

 

접근 방법 및 풀이

---

완전 탐색 문제이다.

구름이 있는 자리를 찾으면 그 주변 상하좌우, 대각선 까지 인접한 부분의 숫자를 +1 해주는 방식으로 풀면 된다.

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    static int[] dx = new int[] {1, -1, 0, 0, 1, -1, 1, -1};
    static int[] dy = new int[] {0, 0, 1, -1, 1, -1, -1, 1};
    static int[][] map, scoreboard;
    static boolean[][] visited;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        scoreboard = new int[N][N];
        visited = new boolean[N][N];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j] == 1) {
                    continue;
                }
                scoreboard[i][j] = dfs(i, j, 0);
            }
        }

        int result = 0;
        for(int scores[] : scoreboard) {
            for(int score : scores) {
                if(score == K) {
                    result++;
                }
            }
        }
        System.out.println(result);
    }
    public static int dfs(int x, int y, int count) {
        visited[x][y] = true;
        for(int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
                if(!visited[nx][ny] && map[nx][ny] == 1) {
                    count++;
                }
            }
        }
        return count;
    }
}