백준 14472 자바 - 休憩スペース (Refreshment Area) (BOJ 14472 JAVA)

문제 : boj14472

 

 

  N, M, D 모두 최대 100 까지이므로 모든 경우를 다 살펴본다 해도 O(2NMD) 정도이다(2는 가로, 세로). 그러니 그냥 어렵게 DP같은걸 끼얹을 필요 없이 그냥 브루트포스를 활용한 구현문제로 보면 된다.

 

  가로, 세로 좌표 [0~N-D, 0~M-D] 의 모든 지점에 대해서 그 우측으로 D번동안 장애물이 없다면 성공, 마찬가지로 아래쪽으로 D번 동안 장애물이 없다면 성공으로 치면 된다. 이하 그림에서는 N=3, M=3, D=2 인 경우 나올 수 있는 모든 경우를 그려보았고 그 중 장애물에 걸리지 않은 경우를 노란색, 걸린 경우를 회색으로 나타냈다. 이걸 코드로 구현만 하면 된다!

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        boolean[][] arr = new boolean[r][c];
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                arr[i][j] = row.charAt(j)=='#'?false:true;
            }
        }

        int cnt = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (c-j >= n) {
                    int k = 0;
                    while (k<n) {
                        if (!arr[i][j+k]) break;
                        k++;
                    }
                    if (k==n) cnt++;
                }

                if (r-i >= n) {
                    int k = 0;
                    while (k<n) {
                        if (!arr[i+k][j]) break;
                        k++;
                    }
                    if (k==n) cnt++;
                }
            }
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}