[백준] 1236번: 성지키기

링크: https://www.acmicpc.net/problem/1236

1236번: 성 지키기

성 지키기

문제

영식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다. 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.

성의 크기와 경비원이 어디있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다.

출력

첫째 줄에 추가해야 하는 경비원의 최솟값을 출력한다.

---

문제 접근

문제를 이해하기가 어려워서 여러번 읽었던거 같다. 결국은 2차원배열의 형태로 들어온 성의 구조에서 행과 열로 탐색을 하여 접근하는것이 베스트라는 결론이 나왔다.

 

가령 문제 예시에서

. . . .

. . . .

. . . .

. . . .

이라면 n과 m은 4이고 x는 없으니 모두 경비원이 없는 비어있는 성이된다.

우선은 행을 기준으로 탐색하고 다음은 열을 기준으로 탐색을 하면 된다. 그리고 각각의 기준으로 탐색하여 비어있는 행과 열을 카운트하고 가장 큰 값을 반환해 주면 된다.

---

코드

"""
백준 알고리즘 1236번: 성 지키기
https://www.acmicpc.net/problem/1236
"""
import sys

def calc(n,m,castle):
    row_cnt = 0
    col_cnt = 0
    
    # 행을 기준으로 탐색
    for i in range(n):
        check = True
        for k in range(m):
            if castle[i][k] == 'X': #경비원이 있는 행이라면 스탑
                check = False
                break
        if check: row_cnt += 1

    # 열을 기준으로 탐색
    for i in range(m):
        check = True
        for k in range(n):
            if castle[k][i] == 'X': #경비원이 있는 열이라면 스탑
                check = False
                break
        if check: col_cnt += 1

    # 체크한 행과 열의 필요한 경비원의 수 중 큰 값을 반환
    return max(row_cnt, col_cnt)


def main():
    # 입력값을 받는 부분
    n,m = sys.stdin.readline().split()
    n = int(n); m = int(m)
    castle = []
    for i in range(n):
        castle.append(list(sys.stdin.readline()[:-1]))

    print(calc(n,m,castle))

if __name__ == "__main__":
    main()