[Baekjoon] 2232_지뢰

Silver II

문제(출처: https://www.acmicpc.net/problem/2232)

---

< 지뢰 >

 

문제 풀이 

 

지뢰의 힘이 큰 지뢰부터 터트리면서 남아있는 지뢰들을 다 터트린다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

public class _2232_ { // 지뢰

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(bf.readLine());

		int arr[] = new int[n];
		boolean visited[] = new boolean[n];

		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0]) {
					return o1[1] - o2[1];
				}
				return o2[0] - o1[0];
			}
		});

		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(bf.readLine());
			arr[i] = num;
			queue.add(new int[] { num, i });
		}

		ArrayList<Integer> result = new ArrayList<>();
		int cnt = 0;

		while (!queue.isEmpty()) {
			int info[] = queue.poll();

			if (!visited[info[1]]) {
				result.add(info[1] + 1);
				visited[info[1]] = true;
				cnt += 1;

				int temp = info[1];
				while (temp - 1 >= 0 && !visited[temp - 1] && arr[temp - 1] < arr[temp]) {
					visited[temp - 1] = true;
					cnt += 1;
					temp -= 1;
				}

				temp = info[1];
				while (temp + 1 < n && !visited[temp + 1] && arr[temp + 1] < arr[temp]) {
					visited[temp + 1] = true;
					cnt += 1;
					temp += 1;
				}
			}
			if (cnt == n) {
				break;
			}
		}
		Collections.sort(result);

		for (int i = 0; i < result.size(); i++) {
			bw.write(result.get(i) + "\n");
		}
		bw.flush();
	}
}

변수)
n : 지뢰 개수
arr : 지뢰 힘
visited : 지뢰 터진 여부
queue : 우선순위 큐 <지뢰 힘, 지뢰 번호>
result : 직접 터트려야 하는 지뢰의 번호
cnt : 터진 지뢰 개수

 

지뢰의 개수를 입력받는다. 지뢰의 개수만큼 지뢰의 힘을 입력받으면서 arr에 정보를 저장하고, 우선순위 큐에 [지뢰 힘, 지뢰 번호]를 저장한다. 여기서 우선순위는 지뢰 힘이 큰 것을 우선으로, 지뢰 힘이 같다면 지뢰 번호가 작은 것을 우선으로 한다. 우선순위 큐가 빌 때까지 다음 과정을 반복한다.

1) 우선순위 큐 poll

2) 아직 터지지 않은 지뢰라면 result에 지뢰 번호 추가 및 터진 여부 표시, cnt+1 

3) 좌우 지뢰에 연쇄 반응

4) 모든 지뢰가 다 터졌다면 종료

 

result를 오름차순으로 정렬 후 출력

---

---