25469. 페인트칠

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AZlP2QbavInHBIO0&categoryId=AZlP2QbavInHBIO0&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

 

H x W 크기의 배열이 모두 흰색인 '.'로 채워져 있다고 생각했을 때,

입력으로 받는 목표 배열로 만들기 위해 필요한 최소 검정색 칠 '#' 횟수 구하기

단, 검정색 칠은 한 번에 하나의 열 또는 하나의 행을 칠할 수 있음

 

알고리즘은 간단했다.

일렬로 된 검정색 라인이 몇 개 있는지 세어보았는데, 단순 갯수 세기로는 오답이 나왔다.

 

예외처리가 필요했다.

예를 들면, 5 x 3의 배열이

###
###
###
###
###

위와 같이 되게끔 칠해야 한다고 할 때, 일렬로 검은 칠 된 라인을 모두 세는 게 아니라,

 

만약 (열을 기준으로 검은 색 칠해야 하는 횟수)가 W와 같고, (행을 기준으로 검은 색 칠해야 하는 횟수)가 H와 같다면,

(열을 기준으로 검은 색 칠해야 하는 횟수)와 (행을 기준으로 검은 색 칠해야 하는 횟수) 중 최솟값을 답으로 내야 한다.

 

T = int(input())

for t in range(T) :
    H, W = map(int, input().split())

    canvas = []
    h_ans = 0
    for h in range(H) :
        line = list(input())
        canvas.append(line)

        all_black = True
        for l in line :
            if l == '.' :
                all_black = False
        if all_black : h_ans += 1
    w_ans = 0
    for w in range(W) :
        all_black = True
        for h in range(H) :
            if canvas[h][w] == '.' :
                all_black = False
        if all_black : w_ans += 1

    if h_ans == H and w_ans == W :
        print(min(h_ans, w_ans))

    else :
        print(h_ans + w_ans)