구름톤 챌린지 2주 Day2 - 구름 찾기 깃발

구름 찾기 깃발 (Java)

 

제출한 답 :

package week2;

import java.util.Scanner;

public class day2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt(); // 격자의 크기 N
        int K = scanner.nextInt(); // 찾고 싶은 깃발의 값 K

        int[][] gameBoard = new int[N][N]; // 게임판

        // 게임판 정보 입력
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                gameBoard[i][j] = scanner.nextInt();
            }
        }

        int kFlagCount = countKFlags(N, K, gameBoard); // 깃발의 개수 계산
        System.out.println(kFlagCount); // 결과 출력

        scanner.close();
    }

    public static int countKFlags(int N, int K, int[][] gameBoard) {
        // 주변 위치 계산을 위한 dy, dx 배열
        int[] dy = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dx = {-1, 0, 1, -1, 1, -1, 0, 1};
        int kFlagCount = 0; // 깃발 개수를 저장할 변수

        // 모든 격자를 돌면서 깃발의 개수를 계산
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (gameBoard[i][j] == 0) { // 현재 위치에 구름이 없는 경우
                    int countClouds = 0; // 주변 구름 개수를 저장할 변수
                    for (int dir = 0; dir < 8; dir++) { // 주변 8방향을 검사
                        int ny = i + dy[dir]; // 주변 위치의 행 인덱스
                        int nx = j + dx[dir]; // 주변 위치의 열 인덱스
                        if (ny >= 0 && ny < N && nx >= 0 && nx < N && gameBoard[ny][nx] == 1) {
                            countClouds++; // 주변에 구름이 있으면 카운트 증가
                        }
                    }
                    if (countClouds == K) { // 주변 구름 개수가 K와 같다면
                        kFlagCount++; // 깃발 개수 증가
                    }
                }
            }
        }

        return kFlagCount; // 최종 깃발 개수 반환
    }
}

왜 버퍼로 하면 오류가 나는지 알 수 없어서... 그냥 스캐너로 풀음..

진짜... 너무 어려워져서 이젠 그냥 못 풀면 마는 거다. 2주차가 이런데 3-4주면 도대체 얼마나 어려워 지는가?ㅎㅎ

 

현재 위치가 0, 0일 때

• 위로 이동: dy[dir] = -1, dx[dir] = 0
• 아래로 이동: dy[dir] = 1, dx[dir] = 0
• 왼쪽으로 이동: dy[dir] = 0, dx[dir] = -1
• 오른쪽으로 이동: dy[dir] = 0, dx[dir] = 1
• 왼쪽 위로 이동: dy[dir] = -1, dx[dir] = -1
• 오른쪽 위로 이동: dy[dir] = -1, dx[dir] = 1
• 왼쪽 아래로 이동: dy[dir] = 1, dx[dir] = -1
• 오른쪽 아래로 이동: dy[dir] = 1, dx[dir] = 1

 

문제 풀이

필요한 개념

• 2차원 배열(행렬, 매트릭스) 에서의 완전 탐색

분석

구름 찾기라는 게임에서 깃발을 세우는 문제입니다. 지뢰 찾기 의 개념을 빌려와 제작한 문제입니다. 2차원 배열 안에서 어떤 칸의 값이 0 이라면, 주위에 1이 몇 개인지 확인하는 문제입니다. 그렇다면, 모든 0인 칸에 대해서 주위에 1 이 몇 개인지 찾아야 하기 때문에 완전 탐색 문제입니다.

그리고 주위에 깃발의 개수가 K 개인 칸의 개수를 세면 됩니다.

문제 풀이

단어 나누기 문제는 문자열 에서 진행되는 완전 탐색 문제였지만, 이 문제는 2차원 배열, 즉 행렬에서 진행되는 완전 탐색 문제입니다. 탐색을 위한 적절한 행렬를 선언할 필요하기 있습니다.

행렬의 어떤 칸의 값이 0이라면, 주변에 1이 몇 개인지 확인해서 값을 갱신하면 문제 풀이는 끝입니다. 단, 주변에 1이 몇 개인지 확인하는 방법으로 DX/DY 기법을 활용할 수 있습니다. 이 기법을 익히면 행렬에서 진행되는 문제는 두려워할 필요가 없습니다.

행렬

사실 알고리즘 문제를 구름톤 챌린지와 함께 처음 배운다고 해도, 2차원 배열 에 대한 개념을 들어봤을 것입니다. 수학적 개념이지만, 프로그래밍에서는 이 개념을 구현한 데이터 구조라고 보시면 됩니다.

• 2차원 배열은 배열 안에 또 다른 배열을 넣는 것으로 이해할 수 있습니다.
• 일종의 격자 상태로 보는 것이 이해하기 쉬우며, 행과 열의 길이가 같을 수도, 다를 수도 있습니다.

자바에서 2차원 배열은 아래와 같이 선언할 수 있습니다.

// Node.js에서의 2차원 배열 생성
int[][] matrix = new int[3][3];
// 행렬의 값 삽입을 반복문으로 수행
for (int i = 0; i < 3; i++) {
	  for (int j = 0; j < 3; j++) {
	      matrix[i][j] = i * 3 + j;
	  }
}
/*
output
[
  [ '0, 0', '0, 1', '0, 2' ],
  [ '1, 0', '1, 1', '1, 2' ],
  [ '2, 0', '2, 1', '2, 2' ]
]
*/

하지만 선언과 달리 데이터를 입력할 때는 아래와 같이 입력하면 편리합니다.

우선 첫째 줄에 N과 M가 입력됩니다. 공백이 있는 2개의 정수를 입력은 다양한 방법으로 받을 수 있지만, 아래의 코드가 제일 간결합니다. 각각의 정수를 입력 받은 뒤에, 줄바꿈 기호를 nextLine() 으로 제거하는 방법입니다.

이후에 N개의 줄에 걸쳐서 입력이 되는 배열을 split() 메소드를 사용하여 배열로 변환한 후, 행렬에 배열 자체를 추가하면 됩니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[][] matrix;
        int N, M, answer;

        N = scanner.nextInt();
        M = scanner.nextInt();
        scanner.nextLine(); // 줄바꿈 기호를 없애줍니다.

        matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            String[] line = scanner.nextLine().split(" ");
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(line[j]);
            }
        }
		}
}

dx/dy 기법

dx/dy 기법은 주로 2차원 배열에서 사용되는 기법입니다. 간단하게 하면 현재 내 위치에서, 상하좌우, 대각선 방향으로 이동이나 탐색을 구현할 때 사용합니다.

이동의 중심은 항상 현재 위치 입니다. 현재 위치에서 상하좌우의 인덱스를 만들어내는 방법이에요. 아까 행렬 선언할 때, 결과가 아래와 같았습니다. 각각의 위치의 인덱스를 표현했죠. 이 인덱스의 arr[1][1] 위치에서 상하좌우의 좌표를 확인해보시면 규칙이 있습니다. 좌우는 열의 좌표가 +1되거나 -1이 되었어요 상하는 행의 좌표가 +1 되거나, -1이 되었습니다.

이 점을 이용한 것이 dx/dy 기법입니다.

arr = 
[
  [ '0, 0', '0, 1', '0, 2' ],
  [ '1, 0', '1, 1', '1, 2' ],
  [ '2, 0', '2, 1', '2, 2' ]
]

arr[1][1] 의 상하좌우의 값은 arr[0][1], arr[2][1], arr[1][0], arr[1][2] 입니다. 이를 인덱스로 표현하면 다음과 같이 표현할 수 있습니다.

int[] dx = {0, 0, -1 -1};
int[] dy = {1, -1, 0, 0};

그리고 각각의 인덱스를 접근할 때, 반복문을 사용하면 됩니다. 아래 코드의 결과를 봤을 때, arr 배열에서 상하좌우를 잘 탐색하고 있는 것을 확인할 수 있습니다.

int[] dx = {0, 0, -1 -1};
int[] dy = {1, -1, 0, 0};

// 시작 위치 설정
int x = 1;
int y = 1;

// 4방향 탐색
for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    System.out.println(nx + " " + ny); // 1 0\n 1 2\n 0 1\n 2 1
}

이 문제는 대각선 방향도 포함하고 있기 때문에, 아래의 8 방향으로 표현할 수 있습니다. 또 탐색을 할 때는 올바른 탐색 위치인지 항상 확인해야 합니다. 이 경우에는 배열 밖을 나가는 탐색을 올바른 탐색 위치가 아니기 때문에, 만약에 다음 탐색할 위치가 2차원 배열 밖이라면 탐색 하지 않게 해야 해요.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
				..code

        int[] dx = {0, 0, 1, 1, 1, -1, -1, -1};
        int[] dy = {1, -1, 1, 0, -1, 1, 0, -1};
				int x = 1;
				int y = 1;
        if (matrix[x][y] == 0) {
            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) {
									..code
                }
            }
		    }
		}
}

완전 탐색

문제를 위해서 필요한 개념을 모두 배웠습니다. 그렇다면 다시 문제로 돌아와서 문제를 구조화 해보면 어떤 칸의 값이 0 이라면, 8방향 을 모두 탐색해서 1의 개수를 찾기만 하면 됩니다.

1. 모든 좌표에 대해서 matrix[x][y] 의 값이 0 인지 확인합니다.
   • 0 이 아니라면, 굳이 탐색할 필요가 없습니다.
2. 0 이라면, 8개의 방향을 모두 탐색합니다. 이때 탐색 가능한 범위인지 확인합니다.
   • 탐색한 matrix[nx][ny] 의 값이 1 이라면 goormcount 를 1 증가시킵니다.
3. 탐색할 때 마다 주변 구름의 개수를 확인하고 그 값이 K이면 answer 변수를 1 증가 시킵니다.
4. 모든 탐색을 종료한 뒤, answer 을 출력하면 끝입니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[] dx = {0, 0, 1, 1, 1, -1, -1, -1};
        int[] dy = {1, -1, 1, 0, -1, 1, 0, -1};
        int[][] matrix;
        int N, M, answer;

        N = scanner.nextInt();
        M = scanner.nextInt();
        scanner.nextLine();

        matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            String[] line = scanner.nextLine().split(" ");
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(line[j]);
            }
        }

        answer = 0;
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                int goormCount = 0;
                if (matrix[x][y] == 0) {
                    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 (matrix[nx][ny] == 1) {
                                goormCount ++;
                            }
                        }
                    }
                    if (goormCount == M) {
                        answer++;
                    }
                }
            }
        }

        System.out.println(answer);
    }
}