[백준/9082] 지뢰 찾기 - 그리디 (Java)

🙋‍♂️들어가며

이번에 학습할 내용은 그리디 응용버젼이다

예제

boj-9082-지뢰찾기

풀이

↙️ ⬇️ ↘️ 이 방향을 생각해보자 먼저 해당문제는 그리디로 풀 수 있겠다

2가지 경우로 나눠보자

1. 지뢰(*)일때 횟수 합산

2-1. 지뢰가 아닐떄 (#) 지뢰를 놓을 수 있는지 검사
2-2. 유효성 검사

*일때는 무조건 cnt++ #라면 앞에서 부터 범위에 맞다면 3가지 방향을 탐색할 수 있도록하고 숫자를 줄여나가며 0이 될시 해당 반복문은 break한다.

testcase_1, testcase_2를 풀어보자

빈칸은 임의로 -라 지정하겠다

빨간색으로 표시한 idx에서 인근 1칸씩 줄일 수 있을 때 차감한다

🙂testcase_1 –> 11122

00122

*

00122

*-

00122

*--

00011

*--*

00011

*--**

🙂testcase_2 –> 23321

02321

*

01221

**

00111

***

00000

****

00000

****-

코드

아래 Java 코드는 그리디 관점에서 접근한 핵심 풀이입니다. 입력 조건과 시간·공간 복잡도를 함께 고려하여 불필요한 연산을 줄이는 방향으로 설계했습니다.

/*
그리디 
*/

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;


public class Main {
	static char[] block;
	static int[] numbers;
	static int N;
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc < T+1; tc++) {
			N = Integer.parseInt(br.readLine());
			String num_arr = br.readLine();
			block = br.readLine().toCharArray();
			numbers = new int[N];
			for (int i = 0; i < N; i++) {
				numbers[i] = num_arr.charAt(i) - '0';
			}
			
			
			lets_find_maximum_bomb();			
		}
		
		
		
	}
	
	
	
	
	
	static void lets_find_maximum_bomb() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			// 1. 지뢰일 때 놓을 수 있는지 검사
			if (block[i] == '*') {
				for (int j = i-1; j <= i+1; j++) {
					if (j >= 0 && j < N) {
						numbers[j]--;
					}
				}
				cnt++;
			}
			// 2-1. 지뢰가 아닐 때 놓을 수 있는지 검사
			else if (block[i] == '#') {
				boolean flag = true;
				for (int j = i-1; j <= i+1; j++) {
					if (j >= 0 && j < N && numbers[j] <= 0) {
						flag = false;
						break;
					}
				}
				// 2-2. 유효성 검사
				if (flag) {
					for (int j = i-1; j <= i+1; j++) {
						if (j >= 0 && j < N) {
							numbers[j]--;
						}
					}
					block[i] = '*';
					cnt++;
				}
			}
		}
		// 3. 출력
		System.out.println(cnt);	
	}
	
	
	
	
	
}

위 구현은 [백준/Java] 9082번 지뢰 찾기 풀이 - 구현 알고리즘의 제약 조건을 만족하도록 자료구조 선택과 반복 범위를 최적화한 결과입니다.