[구름톤 챌린지, Java] 9일차, 폭탄 구현하기(완전탐색)

문제 링크

구름LEVEL

---

접근 방법

이 문제에 핵심

1. 폭탄은 상하좌우 인접한 칸에 영향을 끼칩니다.

2. 폭탄의 영향받은 칸이 '0'이면 +1, '@'이면 +2로 폭탄값을 변화시킵니다.

3. 주어진 폭탄을 다 터트렸을 때 최대 폭탄값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 모든 폭탄을 터트린 뒤 폭탄의 최대값을 탐색합니다.

 

3. 탐색을 통해 얻은 최대 폭탄값을 결과로 출력합니다.

 

 

구현

 

폭탄을 터트릴 때 상하좌우 인접값

 

	(-1, 0)
(0, -1)	폭탄	(0, 1)
	(1, 0)

 

dr[] : {-1, 1, 0, 0} , 상하좌우 y 변경 값

 

dc[] : {0, 0, -1, 1}, 상하좌우 x 변경 값

 

주어진 모든 폭탄을 터트립니다.

 

영향을 받은 칸

 

'0'  : +1

 

'@' : +2

 

'#' : +0

 

모든 폭탄을 터트린 후 모든 칸을 탐색하여 가장 큰 폭탄값을 구합니다.

 

예제입력 1.

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

 

N : 4

 

K : 4

 

🚨 : 폭탄

 

0	0	@	🚨🚨
0	🚨	🚨	0
0	#	0	0
0	0	0	@

 

2. 모든 폭탄을 터트린 뒤 폭탄의 최대값을 탐색합니다.

 

0	1	@(6)	💥💥(2)
1	💥(1)	💥(1)	3
0	#(0)	1	0
0	0	0	@

 

최대값 탐색

 

0	1	6	2
1	1	1	3
0	0	1	0
0	0	0	0

 

3. 탐색을 통해 얻은 최대 폭탄값을 결과로 출력합니다.

 

최대값 : 6

 

 

6을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 띄어쓰기 기준 입력값을 나누었습니다.
• 입력받은 모든 폭탄을 터뜨리는 과정을 진행합니다.
• 모든 폭탄이 터진 후 최대 폭탄값을 탐색합니다.
• 탐색으로 얻은 최대 폭탄값을 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• inSpace함수는 인접한 칸이 땅에 존재하는지 확인하는 함수입니다.

 

결과코드

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());
        char[][] ground = new char[N+1][N+1];	//땅 정보 저장 배열
        int[][] score = new int[N+1][N+1];	//폭탄값 저장 배열
        for(int i=1;i<=N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=N;j++){
                ground[i][j] = st.nextToken().charAt(0);
            }
        }
        //상하좌우 인접 y, x 변경값
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        //모든 폭탄 터뜨리기
        for(int i=0;i<K;i++){
            st = new StringTokenizer(br.readLine()," ");
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            //폭탄의 위치 값 변경
            if(ground[y][x] == '0'){
                score[y][x]++;
            }else if(ground[y][x] == '@'){
                score[y][x] += 2;
            }
            //폭탄 인접한 칸 값 변경
            for(int j=0;j<4;j++){
                int tempY = y + dr[j];
                int tempX = x + dc[j];
                if(inSpace(tempY,tempX, N)){
                    if(ground[tempY][tempX] == '0'){
                        score[tempY][tempX]++;
                    }else if(ground[tempY][tempX] == '@'){
                        score[tempY][tempX] += 2;
                    }
                }
            }
        }
        //가장 큰 폭탄값 탐색
        int result = 0;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                result = Math.max(result, score[i][j]);
            }
        }
        //최대 폭탄값 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        br.close();
        bw.close();
    }
    //상하좌우 인접한 칸이 땅에 존재하는지 확인하는 함수
    static boolean inSpace(int y, int x, int n){
        if(y > 0 && y <= n && x > 0 && x <= n){
            return true;
        }
        return false;
    }
}

 

---

느낀 점

 

문제를 접근할 때 폭탄 자신의 위치의 폭탄값을 변경해주지 않아서 해당 문제를 찾는데 시간을 사용하였습니다.

 

코드를 작성할 때에는 문제를 잘 분석하고 짜는 것이 중요하다는 것을 깨닫게 되었습니다.