problem
https://www.acmicpc.net/problem/2967
Idea
브루트 포스, 누적합
처음에 문제를 읽었을 때 건물 바닥의 모양은 항상 정사각형이니
좌측 상단의 한 점에서 우측 대각선 아래로 스캔하여 정사각형을 하나 구하고, 우측 하단의 한 점에서 좌측 대각선 위로 스캔하여 정사각형을 하나 구한 뒤 둘의 넓이와 실제 건물 흔적의 개수를 비교하여 적절한 건물 좌표를 구하면 되겠네!
라고 생각을 하고 바로 풀었는데 당연히 틀렸다. 위의 방법으로는 해결할 수 없는 다음과 같은 반례들이 너무 많았다.
// 한 건물의 좌표가 전체 바닥의 좌측상단이나 우측하단에 존재하지 않는 경우
5 5
.....
xxxx.
xxxxx
xxxxx
xxxx.
문제를 계속 풀어보면서 두 건물의 좌표를 구하는 것이 아닌 두 건물의 중복된 넓이를 구하는 것이 문제의 포인트라고 생각했고 누적합을 통해 문제를 풀이했다.
step 1
우선 건물 바닥이 있는 좌표를 1, 바닥이 없는 좌표를 0 으로 하는 행렬을 대상으로 가로 방향과 세로 방향으로 총 두번의 누적합을 구했다.
다음과 같은 입력이 들어 왔을 때의 누적합 리스트는 다음과 같다.
// input
.....
xxx..
xxxx.
xxxx.
.xxx.
// prefix sum
0 0 0 0 0 0
0 0 0 0 0 0
0 1 2 3 3 3
0 2 4 6 7 7
0 3 6 9 11 11
0 3 7 11 14 14누적합 리스트에서 (x, y)의 값은 (0, 0)부터 (x, y) 까지의 모든 값을 더한 값이 된다.
step 2
바닥은 항상 정사각형이기 때문에 출발 좌표에서부터 바닥의 길이 l을 1부터 1씩 증가시키면서 (x+l, y)과 (x, y+l)의 좌표를 확인했을 때, 두 좌표가 모두 x이면 출발 좌표에 l의 길이를 갖는 건물이 존재할 수 있다.
위와 같은 방법으로 모든 좌표 값에 대해 가능한 건물 바닥의 최대 길이를 구한 뒤 candidate라는 리스트에 (y, x, l)라는 형태로 삽입했다.
step 3
구한 누적합 리스트와 누적합을 통해 실제 가능한 두 건물 바닥을 구했다.
우선 candidate 리스트를 역정렬했을 때 첫 번째 원소의 길이 값 l의 제곱 값이 건물 바닥의 전체 넓이와 같으면 두 건물은 같은 좌표에 같은 길이로 세워진 것이 된다. 따라서 이 경우 첫 번째 원소의 (y, x, l) 값을 두번 출력하고 종료했다.
위가 진행되지 않을 경우 두 건물이 다른 좌표에 지어졌음을 의미한다. 조합을 통해 두 좌표 a, b를 구하고 이 때, a.l^2 + b.l^2 - (a와 b의 중복되는 넓이) == 건물 바닥의 전체 넓이 이면 해당 두 좌표에 건물이 세워진 것이 된다.
(사진)
a.l^2와 b.l^2은 쉽게 구할 수 있고 두 건물의 중복되는 넓이를 구하는 것이 문제의 포인트가 되는데 이를 이전에 구한 누적합 리스트를 통해 구했다.
(사진)
위와 같은 방법으로 (좌측 건물의 넓이) - a - b + c 를 하면 중복된 넓이를 구할 수 있고, 각 알파벳은 해당 좌표의 누적합 리스트에서 해당 좌표 값에 접근하면 얻을 수 있다.
Code
import sys
from itertools import combinations
input = sys.stdin.readline
R, C = map(int, input().split())
board = list()
board.append(['.' for _ in range(C+1)])
for _ in range(R):
board.append(['.'] + list(input().rstrip()))
prefix = [[ 1 if board[i][j] == 'x' else 0 for j in range(C+1)] for i in range(R+1)]
for i in range(R+1):
for j in range(C):
prefix[i][j+1] += prefix[i][j]
for j in range(C+1):
for i in range(R):
prefix[i+1][j] += prefix[i][j]
candidate = []
for i in range(1, R+1):
for j in range(1, C+1):
if board[i][j] == 'x':
y, x, cnt = i, j, 1
while y < R+1 and x < C+1 and board[y][j] == 'x' and board[i][x] == 'x':
if prefix[y][x] - prefix[y][j-1] - prefix[i-1][x] + prefix[i-1][j-1] < cnt**2:
break
y += 1
x += 1
cnt += 1
candidate.append((i, j, cnt-1))
temp = sorted(candidate, key=lambda x:-x[2])
if temp[0][2] ** 2 == prefix[R][C]:
print(*temp[0])
print(*temp[0])
exit(0)
for p1, p2 in combinations(candidate, 2):
find = p1[2]**2 + p2[2]**2
ys, ye, xs, xe = 0, 0, 0, 0
if p1[0] < p2[0]:
ys = p2[0] - 1
else:
ys = p1[0] - 1
if p1[0]+p1[2] < p2[0] + p2[2]:
ye = p1[0] + p1[2] - 1
else:
ye = p2[0] + p2[2] - 1
if p1[1] < p2[1]:
xs = p2[1] - 1
else:
xs = p1[1] - 1
if p1[1]+p1[2] < p2[1] + p2[2]:
xe = p1[1] + p1[2] - 1
else:
xe = p2[1] + p2[2] - 1
find -= (prefix[ye][xe] - prefix[ys][xe] - prefix[ye][xs] + prefix[ys][xs])
if find == prefix[R][C]:
print(*p1)
print(*p2)
exit(0)Comment
사실 이 문제를 6개월 전에 풀었는데 다시 풀려고 하니 어떻게 풀어야 할 지 생각이 나지 않았다. 푼 문제를 꾸준히 그리고 다시 보면 확실히 이해할 수 있도록 정리해야겠다고 생각했다.
처음에 문제를 풀기 시작했을 때는
이 문제는 무슨 좌표 값을 (1, 1) 부터 시작하네. 다 아는 사람들끼리 왜 이런데?
라고 생각을 했는데, 누적합을 사용해야 한다는 것을 깨닫고 난 후에는 출제자에게 감사함을 느꼈다.
