[구름톤 챌린지] Day7 구름 찾기 깃발 (Java)

구름LEVEL

 

===문제 설명===

구름 찾기 게임은 한 변의 길이가 n인 격자 모양의 게임판 m에서 진행하는 게임이다.

게임판 일부 칸에는 구름이 숨겨져 있습니다.

구름 찾기 게임의 제작자인 플레이어는 조금 더 쉽게 구름을 찾을 수 있도록 도와주는 깃발을 게임판 위에 설치하려고 한다.

깃발은 구름이 없는 칸이면서, 상하좌우와 대각선으로 인접한 여덟 칸 중 구름이 하나 이상 있는 칸에만 설치할 수 있다.

이렇게 설치한 깃발에는 인접한 여덟 칸 중 구름이 있는 칸의 개수에 해당하는 값이 적힙니다.

 

플레이어는 깃발을 세울 수 있는 모든 칸에 깃발을 세워두었다. 

문득, 플레이어는 깃발 중 값이 k인 깃발이 몇 개 있는지 궁금해졌다. 

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

 

입력

4 2// n k

0 0 0 1 // 각 칸이 0이면 비어있음, 1은 구름을 나타냄

0 0 1 0

0 0 1 0

0 1 1 1

-> 게임판의 크기 : n*n,  찾고 싶은 깃발의 값 k

---

🌟 T I P 🌟

• 모든 칸을 검사해 값을 찾는 완전 탐색 문제입니다.
• 모든 칸을 돌면서 8방향을 조사해야 하므로 방향 배열 dx, dy를 만들어 이용합니다.

 

🔖 풀이과정   

1. 일단 주어진 구름 위치를 2차원배열에 저장해줍니다.

int[][] goorm = new int[n][n]; // n*n칸의 2차원 배열 생성 -> 구름 저장
for(int i=0;i<n;i++){
    input = br.readLine().split(" ");//주어진 입력값을 한줄 받아와(readLine()) -> " "단위로 잘라서 배열로 저장.
    for(int j=0;j<n;j++){
    goorm[i][j]=Integer.parseInt(input[j]);//자른 값을 int형으로 변환
    }
}

 

2. 각 칸에서 조사할 8방향을 배열로 만들어줍니다.

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

//예를 들어
//현재 좌표가 (x,y)라고 할 때,
//현재 방향에서 8방향을 조사하는 방법을 아래처럼 구현할 수 있습니다.
for(int dir=0;dir<8;dir++){
    int nx = x + dx[dir];
    int ny = y + dy[dir];
}

//순서대로 8방향을 탐색할 수 있습니다.
//(x+1,y+1), (x+1,y), (x+1,y-1), (x,y+1), (x,y-1), (x-1,y+1), (x-1,y), (x-1,y-1)
//오른쪽아래    아래      왼쪽아래      오른쪽     왼쪽      오른쪽위     위        왼쪽위

 

3. 만든 dx, dy를 이용해 goorm 배열을 탐색하며 비어있는 칸(구름이 없는 칸)을 찾습니다.

비어있는 칸 주위(8방향)에 몇 개의 구름이 있는지 세어줍니다.

다 세고 해당 칸 주위의 구름이 k개  있다면, answer에 추가해 줍니다.

int answer=0; // 깃발 값이 k인 칸 개수

for(int x=0;x<n;x++){//행
    for(int y=0;y<n;y++){//열
    
        if(goorm[x][y]==0){//비어있는 칸 발견
            int cnt=0;//주위에 구름이 몇개 있는지
            
            for(int dir=0;dir<8;dir++){//8방향 확인
                int nx=x+dx[dir];
                int ny=y+dy[dir];

                if(nx>=0 && nx<n && ny>=0 && ny<n){//(nx,ny)가 행열 범위를 벗어나는지 확인.
                    cnt+=goorm[nx][ny];//구름 개수 추가.
                }
            }
            if(cnt==k) answer++; // 주위 구름 개수가 k라면 answer에 추가.
        }
    }
}

 

4. 깃발 값이 k인 칸을 모두 구했다면 그 칸의 개수 answer를 return 해줍니다.

 

---

전체 코드

import java.io.*;
class Main {
	public static void main(String[] args) throws Exception {
		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[][] goorm = new int[n][n];
		int[] dx={1,1,1,0,0,-1,-1,-1};//8방향
		int[] dy={1,0,-1,1,-1,1,0,-1};
		
		for(int x=0;x<n;x++){
			input = br.readLine().split(" ");
			for(int y=0;y<n;y++){
				if(input[y].equals("1")){//지뢰를 찾으면
					goorm[x][y]=-1;//구름 표시!
					
					for(int dir=0;dir<8;dir++){//주위 8방향의 지뢰가 아닌 칸 -> 깃발 값+1
						int ax=x+dx[dir];//주위 8칸 좌표
						int ay=y+dy[dir];
						
						//범위를 벗어나지 않고, 구름이 있지 않은 칸 -> 깃발 +1
						if(ax>=0 && ax<n && ay>=0 && ay<n && goorm[ax][ay]!=-1){
							goorm[ax][ay]++;
						}
					}
				}
			}
		}
		
		int answer=0;
		for(int x=0;x<n;x++){
			for(int y=0;y<n;y++){
				if(goorm[x][y]==k) answer+=1;
			}
		}
		System.out.println(answer);
	}
}

---

🗞️ 후기 🗞️ 

구름톤 챌린지 문제들을 풀면서 자주 출제되는 유형들만 나와서 좋은 것 같고, 

바로 다음날 풀이가 올라와서 좋았습니다.

 

다들 매일 블록 쌓고 오프라인으로 만납시다! `~`