[구름톤 챌린지] 알고리즘 챌린지 구름찾기깃발

[ 목차 ]

1. 구름찾기깃발 문제

2. 풀이

3. 느낀점

 

구름찾기 깃발 문제

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

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

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

여러분이 플레이어를 대신해 값이 K인 깃발의 개수를 세어주자.

 

예제

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

구름찾기 깃발 예제 그림

 

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

M(3,2)의 깃발 갯수

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

각 칸의 깃발 갯수

 

풀이

우선 게임판의 입력값을 0과 1만 들어오는데 이때 1은 구름이 있는 칸이고 0은 구름이 없는 칸입니다. 

구름이있는 판 주위(상하좌우, 대각선)에 깃발을 꽂아야되므로 우선 구름 위치를 배열에 저장합니다.

 

여기서 board가 게임판이고 Cloud 클래스가 구름의 좌표를 저장해놓은 객체로 location배열에 전부 추가합니다. 추가한 뒤 게임판의 구름 위치 값을 -1로 변경해줍니다. -1로 변경해주는 이유는 후에 깃발을 꽂아야되는데 구름의 위치는 깃발을 꽂지 않기 위해서 입니다.

List<Cloud> locations = new ArrayList<>();
for (int i = 0; i < n; i++) {
    board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    for (int j = 0; j < n; j++) {
        if (board[i][j] == 1) {
            locations.add(Cloud.of(i, j));
            board[i][j] = -1;
        }
    }
}

 

배열에 저장해놨던 구름의 좌표들을 전부 순회하면서 깃발을 꽂습니다. 이때 깃발의 위치는 게임판을 넘어가서는 안되고 구름이 있는 위치에는 깃발을 꽂을 수 없습니다. 이와 같은 경우를 제외하고는 모두 깃발을 꽂아줍니다.

for (Cloud cloud : locations) {
    for (int i = 0; i < dx.length; i++) {
        int cx = cloud.x + dx[i];
        int cy = cloud.y + dy[i];

        if (cx >= 0 && cx < n && cy >= 0 && cy < n && board[cx][cy] != -1) {
            board[cx][cy]++;
        }
    }
}

위의 코드에서 dx,dy 배열이 나오는데 이는 상하좌우, 대각선의 x좌표, y좌표 이동 값을 저장해놓은 배열입니다.

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

 

마지막으로 게임판을 순회하면서 문제에서 요구한 K인 깃발의 갯수를 찾아서 세어주면 정답이 나옵니다.

int answer = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (board[i][j] == findNum) {
            answer++;
        }
    }
}

전체코드

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

/**
 * 구름 찾기 깃발 (195689)
 * 14' 53"
 */
public class Solution {

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

    public static void main(String[] args) {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            System.out.print(solution(reader));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static int solution(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int findNum = Integer.parseInt(st.nextToken());

        int[][] board = new int[n][n];
        List<Cloud> locations = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 1) {
                    locations.add(Cloud.of(i, j));
                    board[i][j] = -1;
                }
            }
        }

        for (Cloud cloud : locations) {
            for (int i = 0; i < dx.length; i++) {
                int cx = cloud.x + dx[i];
                int cy = cloud.y + dy[i];

                if (cx >= 0 && cx < n && cy >= 0 && cy < n && board[cx][cy] != -1) {
                    board[cx][cy]++;
                }
            }
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == findNum) {
                    answer++;
                }
            }
        }

        return answer;
    }

    static class Cloud {

        private final int x;
        private final int y;

        Cloud(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public static Cloud of(int x, int y) {
            return new Cloud(x, y);
        }
    }
}

 

🧐 느낀점

매일매일 꾸준히 풀고있어서 재밌네용