[구름톤 챌린지, Java] 7일차, 구름 찾기 깃발(완전 탐색)

문제 링크

구름LEVEL

---

접근 방법

이 문제에 핵심

1. 한 변의 길이가 N인 격자 M이 주어지며, '1'은 구름이 숨겨져 있고 '0'은 빈 칸입니다.

2. 깃발은 구름이 없는 '0'인 칸에만 설치가 가능합니다.

3. 깃발의 값은 상하좌우, 대각선 모두 포함하여 인접한 구름의 개수입니다.

4. 깃발의 값이 K인 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 격자 M을 탐색하여 깃발의 값이 K인 개수를 탐색합니다.

 

3. 탐색을 통해 얻은 깃발의 개수를 결과로 출력합니다.

 

 

구현

 

깃발이 인접한 구름을 탐색할 때 범위는

 

(-1, -1)	(-1, 0)	(-1, 1)
(0, -1)	깃발	(0, 1)
(1, -1)	(1, 0)	(1, 1)

 

dr : 깃발 인접한 y 변경값

 

{-1, -1, -1, 0, 0, 1, 1, 1}

 

dc : 깃발 인접한 x 변경값

 

{-1, 0, 1, -1, 1, -1, 0, 1}

 

깃발의 값을 구하면

 

1	0	0
0	깃발(0)	1
0	0	1

 

깃발의 값 : 3

 

위 과정을 구름이 없는 칸(0)을 모두 탐색하여 값이 K인 깃발의 개수를 구하면 됩니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

 

N : 4

 

K : 2

 

0	0	0	1
0	0	1	0
0	0	1	0
0	1	1	1

 

2. 격자 M을 탐색하여 깃발의 값이 K인 개수를 탐색합니다.

 

dr : 깃발 인접한 y 변경값

 

{-1, -1, -1, 0, 0, 1, 1, 1}

 

dc : 깃발 인접한 x 변경값

 

{-1, 0, 1, -1, 1, -1, 0, 1}

 

통해서 인접한 구름을 탐색하면

 

 

0	1	2	☁
0	2	☁	3
1	4	☁	4
1	☁	☁	☁

 

3. 탐색을 통해 얻은 깃발의 개수를 결과로 출력합니다.

 

깃발의 값이 2(K)의 개수는 2개입니다.

 

 

2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 입력값들을 띄어쓰기 기준 나눕니다.
• 모든 빈 칸에 깃발을 설치하고, 깃발의 값을 계산합니다.
• 깃발의 값이 K인 개수를 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• inSpace함수는 격자 M에 존재하는지 확인하는 함수입니다.

 

결과코드

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        String[][] M = new String[N][N];
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0;j<N;j++){
                M[i][j] = st.nextToken();
            }
        }
        //인접한 구름 탐색 y변경 값
        int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
        //인접한 구름 탐색 x변경 값
        int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
        int result = 0;
        //모든 깃발의 값 구하기
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(M[i][j].equals("1")){	//구름일 때
                    continue;
                }
                int cnt = 0;
                //인접한 칸 탐색
                for(int d=0;d<8;d++){
                    int tempR = i + dr[d];
                    int tempC = j + dc[d];
                    //인접한 칸에 구름이 존재할 때
                    if(inSpace(tempR, tempC, N) && M[tempR][tempC].equals("1")){
                        cnt++;
                    }
                }
                //해당 깃발의 값이 K일 때
                if(cnt == K){
                    result++;
                }
            }
        }
        //깃발의 값이 K인 개수를 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //격자 M에 존재하는지 확인하는 함수
    static boolean inSpace(int r, int c, int N){
        //격자 M에 존재할 때
        if(r >= 0 && r < N && c >= 0 && c < N){
            return true;
        }
        return false;
    }
}

 

---

느낀 점

 

인접 배열 탐색을 진행하는 과정을 되새기는 계기가 되었습니다.