ABC 337 D번 복기 - 2차원 배열에서 행,열로 연속한 O의 개수를 빠르게 세는 방법(sliding window + prefix sum)

D - Cheating Gomoku Narabe (atcoder.jp)

D - Cheating Gomoku Narabe

 

 

. o x로 이루어진 2차원 배열에서 .을 o로 바꿀 수 있다.

 

이 때 행이나 열로 연속한 o의 개수가 k개가 되도록 최소로 바꾸는 횟수

 

처음에 DFS로 o의 좌표에서 시작해서 .을 o로 바꿔서 해보다가 당연히 시간초과났고

 

그러다가 행이나 열 각각에서 모두 조사해보면 된다는 생각이 들었다

 

여기까지는 좋았음

 

행 한줄에서 어떻게 .을 o로 바꿔야 연속한 o의 개수를 찾을 수 있을까

 

길이가 k인 구간에서 o의 개수와 x의 개수를 세본다.(window)

 

x의 개수가 1개 이상이면 그 구간은 길이가 k인 연속한 o가 될 수 없다.

 

x의 개수가 0개면, 그 구간에서는 (k - (o의 개수))만큼 .을 o로 바꿔야 될 것이다.

 

이런 구간을 왼쪽에서 오른쪽으로 이동시키면서(sliding),

 

한 줄에서 가능한 모든 길이가 k인 구간에 대해서 조사해본다

 

 

 

 

근데 구간의 길이 k가 최악의 경우 20만까지 가능해서 한 구간에서 매번 o,x의 개수를 세면 시간초과 가능성이 높다

 

최초 0번부터 k-1번까지 구간에서 o의 개수와 x의 개수를 모두 세둔다.(prefix sum)

 

위 그림에서 첫 구간에 검정 2개 흰색 1개인데..

 

이제 한칸 옆으로 이동하면, 0번 자리의 검정 1개가 감소할 것이고..

 

k번 자리에 존재하는 검정 or 흰색이 1개 증가할 것이다.

 

따라서 현재 시작점이 i번이라면.. i-1번이 o라면 o의 개수를 1개 감소, x라면 x의 개수를 1개 감소.

 

k-1+i번 자리가 o라면 o의 개수를 1 증가, x라면 x의 개수를 1 증가

 

이렇게 하면 한칸 이동할때마다 O(1)로 o의 개수와 x의 개수를 바로 알 수 있어서..

 

각 구간에서 바꾸는데 필요한 횟수를 바로 알 수 있다.

 

 

 

from sys import stdin

h,w,k = map(int,stdin.readline().split())

maps = [stdin.readline().rstrip() for _ in range(h)]

INF = 1000000000000000000000000000000000

answer = INF

#한 줄에서 연속한 o의 개수가 k개가 되도록 .을 o로 바꾸는 최소 횟수
def check(row,k):

    o = 0
    x = 0

    result = INF

    if len(row) >= k: #한 줄이 k 이상이어야 가능
        
        #먼저 0 ~ k-1 구간에서 o의 개수와 x의 개수를 모두 센다
        for i in range(k):
        
            if row[i] == 'o':
                
                o += 1
            
            elif row[i] == 'x':
                
                x += 1
        
        #한 구간에서 x가 0개여야, 길이가 k인 연속한 o가 될 수 있다
        if x == 0:
            
            if result > k - o:
                
                result = k - o #그러면 (k - (o의 개수))만큼 .을 o로 바꾸면 된다
        
        #이제 1~len(row)-k-1까지 시작점을 이동시킨다
        for i in range(1,len(row)-k-1):
            
            #구간의 시작점이 i일때 i-1번 자리의 o나 x가 사라진다
            if row[i-1] == 'o':
                
                o -= 1
            
            elif row[i-1] == 'x':
                
                x -= 1
            
            #k-1+i번 자리의 o나 x가 추가된다
            if row[k-1+i] == 'o':
                
                o += 1
            
            elif row[k-1+i] == 'x':
                
                x += 1
            
            #마찬가지로 한 구간에서 x가 0개여야 길이가 k인 연속한 o가 가능하다.
            #항상 최솟값으로 갱신
            if x == 0 and result > k - o:
                
                result = k - o
    
    return result

#행에 대해서 모두 체크
for row in maps:

    value = check(row,k)

    if answer > value:

        answer = value

#열에 대해서 모두 체크
for col in zip(*maps):

    value = check(col,k)

    if answer > value:

        answer = value

#모두 체크해도 INF라면, 불가능한 것이므로 -1을 출력
if answer == INF:

    print(-1)

else:

    print(answer)