[BaekJoon] #35307 - 하얀 전파 [Java][C++]

문제 링크

---

1. 아이디어

주어진 격자에 대해 초기엔 모든 칸이 검은색이며 특정 위치를 흰색으로 바꾼 후 전파를 시작해서 전파가 끝났을 때 하얀 칸의 최대 개수와 해당 시간을 구하는 문제로 격자의 크기가 매우 커서 직접 전파를 하는 방식은 어렵다. 시작 칸의 행과 열은 따로 고를 수 있으므로 가로 방향과 세로 방향을 나눠서 생각할 수 있는데, 가로 방향은 1초마다 왼쪽으로 $L$칸, 오른쪽으로 $R$칸씩 전파되므로 시작 칸을 알맞게 골라 양쪽이 동시에 끝나게 하면 1초에 합쳐서 $L + R$칸씩 채우는 것과 같다. 따라서 가로 방향 전체로 전파되는 데 걸리는 최소 시간은 시작 칸을 제외한 $M - 1$칸을 $L + R$로 나눈 몫이며, 이때 나머지가 존재하면 1초가 더 걸린다. $L + R$이 0이어서 가로 방향 진행이 없는 경우 전파가 멈추는 데 걸리는 시간은 0이다. 세로 방향 역시 $N - 1$을 $U + D$로 나눠서 마찬가지로 구할 수 있다. 채울 수 있는 하얀 칸의 수는 가로 방향 진행이 있으면 가로 전체를, 세로 방향 진행이 있으면 세로 전체를 언젠가는 채우므로 둘 다 있으면 $N \times M$, 한쪽만 있으면 그 방향의 길이, 둘 다 없으면 1이다. 전파 시간의 경우 한 번의 전파는 가로나 세로 중 한 방향으로만 퍼지므로 가장 먼 모서리 칸은 가로 방향 전파 시간과 세로 방향 전파 시간을 더한 만큼 걸리고, 이 합이 전체 전파가 끝나는 데 걸리는 최소 시간이다.

---

2. 복잡도

접근	시간	공간
풀이	$O(T)$	$O(1)$

($T$ = 테스트 케이스 수)

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            long n = Long.parseLong(st.nextToken());
            long m = Long.parseLong(st.nextToken());
            long l = Long.parseLong(st.nextToken());
            long r = Long.parseLong(st.nextToken());
            long u = Long.parseLong(st.nextToken());
            long d = Long.parseLong(st.nextToken());

            long ht = (u + d != 0) ? (n - 1 + u + d - 1) / (u + d) : 0;
            long wt = (l + r != 0) ? (m - 1 + l + r - 1) / (l + r) : 0;

            long cnt = 1;
            if (ht != 0) cnt *= n;
            if (wt != 0) cnt *= m;

            sb.append(cnt).append(" ").append(ht + wt).append("\n");
        }

        System.out.println(sb);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        long long n, m, l, r, u, d;
        cin >> n >> m >> l >> r >> u >> d;

        long long ht = (u + d != 0) ? (n - 1 + u + d - 1) / (u + d) : 0;
        long long wt = (l + r != 0) ? (m - 1 + l + r - 1) / (l + r) : 0;

        long long cnt = 1;
        if (ht != 0) cnt *= n;
        if (wt != 0) cnt *= m;

        cout << cnt << ' ' << ht + wt << '\n';
    }
}

---