[BOJ][JAVA] 31418: 스펀지

 

https://www.acmicpc.net/problem/31418

 

BFS로 처음에 접근했으나, W, H, T가 최대 10^6인걸 확인하고 완전탐색이 아닌 걸 알았다... 

---

푸는 동안 사고과정

java

접기

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static long w, h, k, t;
    static int[] di = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dj = {0, 1, 1, 1, 0, -1, -1, -1};
    static long mod = 998244353;
    static long ans;
 
    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        w = Long.parseLong(st.nextToken());
        h = Long.parseLong(st.nextToken());
        k = Long.parseLong(st.nextToken());
        t = Long.parseLong(st.nextToken());
 
        ans = 1;
        for (int i = 1; i <= k; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            // i번째 바이러스 위치
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());
            go(x, y);
        }
 
        System.out.println(ans);
    }
 
    public static void go(long x, long y) {
        long wCase = Math.min(w, x + t) - Math.max(1, x - t) + 1;
        long hCase = Math.min(h, y + t) - Math.max(1, y - t) + 1;
 
        ans = (ans * wCase) % mod;
        ans = (ans * hCase) % mod;
    }
}

말이 좀 어렵다.

대각선도 이동할 수 있기 때문에, t초일 때 이동할 수 있는 범위는 정사각형이 된다. 또한 각 바이러스가 독립적이기 때문에 각 바이러스의 이동 경우의 수를 다 각각 곱해버리면 된다.

 

이동 범위가 곧 이동 경우의 수가 되므로, 가로와 세로 이동범위를 사각형 형태로 곱해서 처리하면 된다.

가로 이동범위는 [max(1,x−T),min(W,x+T)](왼쪽끝에서 오른쪽 끝까지) 세로 이동범위는 [max(1,y−T),min(H,y+T)] (맨 위에서 맨 아래까지) 다.

 

이 두 이동범위를 곱하면 해당 바이러스가 독립적으로 차지할 수 있는 경우의 수를 알 수 있게 된다. 처음 문제를 읽었을 때 분포의 개념이 이거라는 게 바로 이해가 되지않아 더 어려웠다.

 

max, min을 사용한 이유는 W, H를 넘어가지 않도록 해야되니까 유효성 체크 개념으로 넣어뒀다.

 

ans에는 누적곱을 해야되는데, 문제에서 mod 값을 줬기 때문에 매번 곱할 때마다 mod를 해줘야한다.

 

이게 조합인 걸 떠올리지 못했을 경우에는 아예 못풀었을 것 같다.

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!