백준 9082번 - 지뢰찾기

문제

백준 9082번 - 지뢰찾기

아이디어

왼쪽 또는 오른쪽부터 지뢰를 놓을 수 있는지 확인한다.

코드 구현 - 자바

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

public class BJ_9082 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());

            char[] arr = br.readLine().toCharArray();
            char[] block = br.readLine().toCharArray();

            int[] number = new int[n];
            for (int j = 0; j < n; j++) {
                number[j] = arr[j] - '0';
            }

            int ans = 0;

            for (int j = 0; j < n; j++) {
                // 1
                if (block[j] == '*') {
                    for (int k = j - 1; k <= j + 1; k++) {
                        if (k >= 0 && k < n) {
                            number[k]--;
                        }
                    }
                    ans++;
                }
                else {
                    // 2
                    boolean flag = true;
                    for (int k = j - 1; k <= j + 1; k++) {
                        if (k >= 0 && k < n && number[k] <= 0) {
                            flag = false;
                            break;
                        }
                    }

                    if (flag) {
                        for (int k = j - 1; k <= j + 1; k++) {
                            if (k >= 0 && k < n) {
                                number[k]--;
                            }
                        }
                        block[j] = '*';
                        ans++;
                    }
                }
            }

            System.out.println(ans);
        }
    }
}

1

• 현재 위치에 지뢰를 놓을 수 있는지 확인한다.
• 이미 지뢰가 있는 경우, 현재 위치 포함 인접한 앞뒤 인접한 곳의 숫자들을 하나씩 감소시켜준다.

2

• 지뢰가 없는 경우, 이 위치에 지뢰를 놓을 수 있는지 확인한다.
• 현재 위치 포함 앞뒤 인접한 곳의 숫자가 하나라도 0 이하이면, 이 위치에는 지뢰를 놓을 수 없다.
• 지뢰를 놓을 수 있다면, 지뢰를 놓고 현재 위치 포함 앞뒤 인접한 곳의 숫자를 하나씩 감소시켜준다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)