[백준] #1236 성 지키기(python)

📌문제

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

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

입력

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

출력

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

예제 입력1

4 4
....
....
....
....

예제 출력1

4

예제 입력2

3 5
XX...
.XX..
...XX

예제 출력2

0

예제 입력3

5 8
....XXXX
........
XX.X.XX.
........
........

예제 출력3

3

백준 1236번 문제

💡Idea

추가해야 하는 경비원👮‍♂️의 최솟값은 경비원이 한 명도 존재하지 않는 행의 개수와 열의 개수 중 더 큰 값입니다.

예를 들어 살펴봅시다!

위와 같이 5X8 성이 있다고 합시다.

X표가 있는 부분은 경비원이 존재하는 부분이며, 경비원이 한 명도 존재하지 않는 행과 열들은 빨간 화살표로 표시되어 있습니다.

이 때, 경비원을 한 명만 배치하면 하나의 행과 하나의 열을 채울 수 있습니다.

그럼 모든 열에는 최소 한 명의 경비원이 있게 되고, 그냥 남은 두 개의 열의 아무데나 경비원을 배치하면 됩니다.

우리는 경비원이 한 명도 없는 열과 행을 찾고, 열과 행을 함께 채울 수 있도록 경비원을 배치하고, 남은 열 혹은 행을 채울 수 있는 경비원을 배치하면 됩니다.
즉, 경비원이 한 명도 없는 열의 개수와 행의 개수 중 큰 값을 선택하면 됩니다.

💻코드

• ⏰ 시간 : 68 ms / 메모리 : 30840 KB

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
securities = [input() for _ in range(N)] # 입력
row = set() # 경비원이 있는 행을 저장하는 집합
col = set() # 경비원이 있는 열을 저장하는 집합
for i in range(N):
    for j in range(M):
        if securities[i][j] == 'X': # 경비원이 있는 곳의 열과 행을 집합에 추가
            col.add(i)
            row.add(j)
print(max(N - len(col), M - len(row))) # 경비원이 없는 열과 행의 가수 중 큰 값 출력