[java] 구름톤 7일차. 구름 찾기 깃발

문제

구름 찾기 게임은 한 변의 길이가 N인 격자 모양의 게임판 M에서 진행하는 게임이다. 게임판의 일부 칸에는 구름이 숨겨져 있고, 게임판에 숨겨진 모든 구름의 위치를 찾으면 게임에서 승리할 수 있다.
구름 찾기 게임의 제작자인 플레이어는 조금 더 쉽게 구름을 찾을 수 있도록 도와주는 깃발을 게임판 위에 설치하려고 한다. 깃발은 구름이 없는 칸이면서, 상화좌우와 대각선으로 인접한 여덟 칸 중 구름이 하나 이상 있는 칸에만 설치할 수 있다. 이렇게 설치한 깃발에는 인접한 여덟 칸 중 구름이 있는 칸의 개수에 해당하는 값이 적힌다.
플레이어는 깃발을 세울 수 있는 모든 칸에 깃발을 세워두었다. 문득, 플레이어는 깃발 중 값이 K인 깃발이 몇 개나 있는지가 궁금해졌다. 여러분이 플레이어를 대신해 값이 K인 깃발의 개수를 세어주자.

입력

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

출력

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

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        int[][] board = new int[N][N];

        for (int i = 0; i < N; i++) {
            String[] row = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(row[j]);
            }
        }

        int count = 0;

        // 8방향으로 검사
        int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                // 현재 칸이 0인 경우에만 검사
                if (board[r][c] == 0) {
                    int cloudCount = 0;
                    for (int d = 0; d < 8; d++) {
                        int nr = r + dr[d];
                        int nc = c + dc[d];
                        // 인덱스가 유효하고 해당 칸이 구름인 경우 카운트 증가
                        if (nr >= 0 && nr < N && nc >= 0 && nc < N && board[nr][nc] == 1) {
                            cloudCount++;
                        }
                    }
                    // 카운트가 K와 일치하면 깃발 카운트 증가
                    if (cloudCount == K) {
                        count++;
                    }
                }
            }
        }

        System.out.println(count);
    }
}

사용된 알고리즘은

 

1. 완전 탐색 알고리즘

 

완전 탐색(Exhaustive Search)은 가능한 모든 경우를 하나씩 시도하며 원하는 결과를 찾는 알고리즘입니다. 이 방법은 모든 가능성을 고려하기 때문에 정확한 해답을 구할 수 있지만, 경우의 수가 많거나 입력의 크기가 큰 경우에는 실행 시간이 길어질 수 있습니다.

완전 탐색은 다양한 형태로 적용될 수 있습니다. 여기서는 몇 가지 주요한 형태에 대해 설명하겠습니다.

1. 백트래킹: 조합 최적화나 조건을 만족하는 모든 해를 찾는 경우에 사용됩니다. 가능한 모든 경우를 확인하되, 어떤 조건을 만족하지 않는 경우 더 이상 해당 분기를 탐색하지 않고 되돌아가는 방식입니다. 대표적으로 N-Queens 문제나 스도쿠 문제 등이 백트래킹 알고리즘을 활용하는 예시입니다.
2. 비트 마스크: 이진수의 비트 연산을 활용하여 모든 부분 집합이나 모든 조합을 생성하는 방식입니다. 비트 마스크를 사용하면 루프를 돌며 조합을 생성하는데 사용되는 수행 시간을 크게 줄일 수 있습니다.
3. 완전 탐색 트리: 가능한 모든 선택지를 나타내는 트리 구조를 생성하여 해결하는 방식입니다. 각 선택마다 가지가 나뉘어 각각의 분기를 따라가며 해를 찾습니다. 백트래킹과 유사하지만, 완전 탐색 트리는 일반적으로 모든 경우의 수를 포함하는 구조를 말합니다.
4. 재귀 함수: 재귀적으로 가능한 모든 경우를 탐색하는 방법입니다. 기본 단계(base case)와 재귀적 단계(recursive case)로 나누어 구현하며, 재귀 호출을 통해 가능한 모든 경우를 탐색합니다.

 

2. 8방향

8방향 검사(8-way, Eight-Directional Search)는 2차원 격자나 배열에서 한 지점을 중심으로 주변의 8개의 인접한 지점을 검사하는 방법입니다. 이 방법은 대각선 방향까지 모두 검사하므로 주변의 모든 방향을 고려해야 할 때 유용합니다.

8방향 검사는 컴퓨터 비전, 그래픽 처리, 게임 개발 등 다양한 분야에서 활용됩니다. 대표적인 활용 사례는 이미지 처리에서 주변 픽셀을 분석하거나, 게임에서 유닛의 주변 환경을 확인하는 등이 있습니다.

8방향 검사는 주로 두 가지 방식으로 구현할 수 있습니다:

1. 방향 배열: 주어진 좌표에서 8개의 방향을 미리 정의한 배열을 사용하여 각 방향으로의 이동을 계산합니다. 일반적으로 (1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)과 같이 미리 설정된 방향 벡터를 사용합니다. 이렇게 방향을 미리 정의해 놓으면 반복문 안에서 각 방향에 대해 쉽게 검사를 수행할 수 있습니다.
2. 델타 배열: 주어진 지점에서 8방향으로의 상대적인 이동을 나타내는 델타 값들을 미리 정의한 배열을 사용합니다. 주로 (dx, dy)와 같은 형태로 표현되며, 각각 x와 y 좌표의 변화량을 의미합니다. 이렇게 델타 값을 사용하면 현재 위치에 (dx, dy)를 더하여 다음 위치를 계산할 수 있습니다.

8방향 검사와 완전 탐색을 이번기회에 시도해보게 되어서 좋았다.