[코드트리] 연쇄로 터지는 폭탄

 

https://www.codetree.ai/training-field/search/problems/series-of-bombs-detonating/description?utm_source=clipboard&utm_medium=text&page=9&pageSize=5

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

완전탐색, 시뮬레이션 문제이다.

 

1. 입력 받기: 폭탄의 개수와 각 폭탄의 위치를 입력 받는다.

이때, 폭탄의 위치 인덱스를 배열에 저장하는데 이유는 폭탄의 위치 N이 최대 1,000,000,000까지이므로 예를 들어

boolean[] isBomb=new boolean[1,000,000,001];

 

으로 해서 폭탄의 위치에 true, false하면 오버플로우가 나기 때문이다. 

 

2. 폭탄 위치 정렬: 폭탄 위치를 오름차순으로 정렬

 

3. 최대 폭발 계산: 모든 폭탄 위치에서 시작하여 최대 폭발 가능한 폭탄의 수를 계산

• 이때, 폭탄이 연쇄적으로 폭발이 일어나므로 특정 폭탄을 기준으로 재귀적으로 폭발을 시뮬레이션한다.
• 폭발 범위 내의 폭탄이 이미 폭발했는지 확인하고, 아직 폭발하지 않았다면 폭발 시킨다.
• 폭발이 일어난 후, 범위를 확장하여 양쪽으로 재귀적으로 추가 폭발을 시도합니다.

폭발이 일어났는지 여부는 boolean[] exploded = new boolean[N]의 true, false로 계산한다.

 

4. 폭발된 폭탄 수 계산: count 함수를 통해 폭발된 폭탄의 수를 세어 결과를 출력한다.

 

전체 코드

 

import java.util.*;

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

        for (int i = 0; i < N; i++) {
            bombs[i] = scanner.nextInt();
        }

        Arrays.sort(bombs);

        int maxExplosions = 0;

        for (int i = 0; i < N; i++) {
            boolean[] exploded = new boolean[N];
            explode(bombs, i, exploded, 1);
            maxExplosions = Math.max(maxExplosions, count(N, exploded));
        }

        System.out.println(maxExplosions);
    }

    private static void explode(int[] bombs, int start, boolean[] exploded, int range) {
        exploded[start]=true;
        int i=1;
        boolean canGo=false;
        while(start-i>=0&&bombs[start]-bombs[start-i]<=range){
            if(exploded[start-i]){
                break;
            }
            exploded[start-i]=true;
            i++;
            canGo=true;
        }
        if(canGo)
            explode(bombs,start-(i-1),exploded,range+1);
        i=1;
        canGo=false;
        while(start+i<bombs.length&&bombs[start+i]-bombs[start]<=range){
            if(exploded[start+i]){
                break;
            }
            exploded[start+i]=true;
            i++;
            canGo=true;
        }
        if(canGo)
            explode(bombs,start+i-1,exploded,range+1);
    }

    private static int count(int n, boolean[] exploded){
        int count=0;
        for(int i=0;i<n;i++){
            if(exploded[i])
                count+=1;
        }
        return count;
    }
}