문제
https://www.acmicpc.net/problem/30027
30027번: 비밀의 화원
첫째 줄에 정수 $N(1\le N\le 4\,000)$과 정수 $M(1\le M\le 100\,000)$과 정수 $K(1\le K\le\min(N\times M,1\,000))$가 공백으로 구분되어 주어진다. 둘째 줄부터 $K$개의 줄에 유진이가 꽃을 심은 칸의 위치를 의미하
www.acmicpc.net
풀이
인풋이 작다면 BFS로 간단하게 구할 수 있었을 것이다. 우린 그래프탐색이 아닌 다른 것으로 접근해봐야한다.
N과 K가 작으므로 이를 이용하면 될 것 같다.
꽃의 좌표가 fx,fy라 하면 i일에 어떤 y값에서 꽃이 핀 x값 영역은 (fx - (i - abs(fy-y)),y) ~ (fx + (i-abs(fy-y),y) 이다. (i-abs(fy-y) >= 0이여야 한다.)
꽃이 여러개 있다해도 영역의 모양과 크기는 영향을 받지 않는다. 단순히 겹칠 뿐이다.
이를 이용해서 모든 y에 대해 꽃이 피는 영역을 구하고, 스위핑으로 모든 x에 대해 꽃이 핀것이 확인된다면 정답을 만족한 다.
스위핑은 다음과 같이 하면 된다.
1, 꽃이 핀 영역을 담은 배열 (편의상 (s,e)꼴의 원소가 들어가 있는 배열 F라하자.)을 정렬한다.
2. F의 첫번째 원소의 s가 시작점이 아니라면 실패한다.
3. F의 첫번째원소의 s,e를 start,end란 변수에 할당한다.
4. F를 순회한다. 지금보는 원소의 s가 end + 1보다 크다면 실패한다.(공백영역이 생긴다.)
만약에 e가 end보다 크다면 end를 e로 갱신해준다.
5. F를 순회한 뒤 end는 끝이여야한다.
이는 복잡도 O(N*K*logK)로 해결 가능하다.
여기서 적당한 i를 찾는 것이 문제인데, 정답이 k였다면 k일에 화원의 모든 칸에 꽃이 핀다고하면, k보다 큰 모든 수도 화원의 모든 칸에 꽃이 핀다. 따라서 매개변수 탐색을 이용해 값을 찾을 수 있다.
하지만 O(log(N+K) * N * K * log(K))의 복잡도는 시간초과가 난다.
여기서 logK를 1로 바꿀 수 있다. 각 매개변수 탐색마다 정렬을 하는게 아니라, 최초 1번만 정렬해서 정렬필요없이 스위핑 할 수 있는 방법이 있다.
i일에 어떤 y값에서 얻어진 정렬된 F가 다음과 같이 있다고하자.
F는 시작점을 기준으로 정렬돼있다.
F = [(s1,e1),(s2,e2),(s3,e3),...,(sk,ek)].(s1 <= s2 <= s3 <= ... <= sk)
i-1일이라면 F는 다음과 같이 될 것이다.
F = [(s1+1,e1-1),(s2+1,e2-1),(s3+1,e3-1),...,(sk+1,ek-1)]
이것 역시 s1+1<=s2+1 <=s3+1<=...<=sk+1이 성립한다.
일반화해서 i-t일이라하자.
F = [(s1+t,e1-t),(s2+t,e2-t),(s3+t,e3-t),...,(sk+t,ek-t)]
이것 역시 t에 관계없이 s1 + t <= s2 + t <= ... <= sk+t가 성립한다.
즉 시간(매개변수)과 관계없이 어떤 y값에서 스위핑할때 순회하는 꽃의 순서는 모두 같다!
각 y값마다 볼 꽃의 순서를 O(N*K*logK)의 복잡도로 매개변수 탐색전에 구해놓으면 O(log(N+K) * N * K)로 매개변수 탐색이 가능하다.
'알고리즘문제풀이' 카테고리의 다른 글
| 백준 5485 평균값 수열 (0) | 2023.10.24 |
|---|---|
| 백준 30094 그래서 나는 사진을 그만두었다 (0) | 2023.09.25 |
| 백준 30160 제곱 가중치 (0) | 2023.09.22 |
| 백준 28102 단순한 그래프와 이상한 쿼리 풀이 (0) | 2023.09.14 |
| 백준 8983 사냥꾼 풀이 (1) | 2023.09.13 |