[백준] 1236. 성 지키기

문제

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

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

입력

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

출력

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

 

---

주어진 상태에서 모든 행과 열에 X가 포함되게 만들기 위한 최소한의 X의 수를 구하는 문제이다.

예제 입출력은 다음과 같다.

 

CASE	INPUT	OUTPUT
1	4 4 .... .... .... ....	4

예제에서 성은 4x4의 크기로, 모두 비어있다.

모든 행에 1개 이상의 X가 포함되도록, 모든 열에 1개 이상의 X가 포함되도록 만들면 다음과 같이 X를 배치할 수 있다.

행마다 1개의 X가 포함되고, 열마다 1개의 X가 포함된다.

 

첫 번째 시도

1. 각 행마다 모든 열에 X가 포함되어 있는지 검사한다.

2. X가 있다면 행 번호를 추가한다.

3. 각 열마다 모든 행에 X가 포함되어 있는지 검사한다.

4. X가 있다면 열 번호를 추가한다.

 

행과 열 번호는 중복이 필요없기 때문에 set에 저장한다.

 

작성 코드

n, m = map(int, input().split())
castle = []
rows = set()
cols = set()

for _ in range(n):
    castle.append(input().replace("", " ").split())

for i in range(n):
    if "X" in castle[i][:]:
        rows.add(i)

for j in range(m):
    if "X" in castle[:][j]:
        cols.add(j)

print(max(n-len(rows), m-len(cols)))

 

하지만 FAIL

 

castle[i][:], castle[:][j]가 틀렸다.

castle은 단순히 길이가 n인 배열이다. castle의 원소는 성의 행이다. 따라서 castle[i][:]는 castle[i]와 같다.

castle[:][j]에서는 castle[:]이 castle과 같기 때문에 castle[:][j]은castle[j]이다.

그래서 결과가 제대로 나오지 않았다.

사실 위와 같은 표현은 numpy의 ndarray를 활용할 때 사용하는 방식이다. n차원의 배열이므로 castle[i, :] 또는 castle[:, j]와 같이 사용한다면 제대로 결과를 얻을 수 있을 것이다.

ndarray와 list를 섞어버린 멍청한 짓을...

 

이중 for문을 피하기 위해 위의 방법으로 해본건데, numpy를 사용해서 푸는 것은 너무 과한 것 같아서 패스~

 

두 번째 시도

그냥 맘편히 단순하게 풀었다.

 

작성 코드

n, m = map(int, input().split())
castle = []
rows = set()
cols = set()

for _ in range(n):
    castle.append(input())

for i in range(n):
    for j in range(m):
        if castle[i][j] == "X":
            rows.add(i)
            cols.add(j)

print(max(n-len(rows), m-len(cols)))

 

---

문제 풀다가 빈 성에 X를 채우는 경우의 수를 생각해봤다.

n, m 중 큰 값을 max, 작은 값을 min이라고 할 때, $_{max}P_{min}*{min}^{(max-min)}$의 식이 성립한다.

 

성의 크기가 $6\times4$라고 가정해보자.

 

마법의 성을 지나

 

열을 기준으로 먼저 채워나간다고 생각해보자.

1. 0 번째 열에서 6개의 행에 X가 들어갈 수 있다. => 6가지

2. 1 번째 열에서 5개의 행에 X가 들어갈 수 있다. => 5가지

3. 2 번째 열에서 4개의 행에 X가 들어갈 수 있다. => 4가지

4. 3 번째 열에서 3개의 행에 X가 들어갈 수 있다. => 3가지

이렇게 0, 1, 2, 3 모든 열에 X를 채울 수 있다.

따라서 경우의 수는 $6\times5\times4\times3 = \,_6P_4$ 가지이다.

 

늪을 건너

 

위의 그림과 같이 X를 채웠다고 하면 남은 행이 두 개 남게 된다. 남은 두 행은 어느 열에 X를 채워도 상관없으므로 경우의 수는 $4\times4$의 가지이다.

따라서 총 경우의 수는 $_6P_4\times4^2$이다.

 

다른 방식으로 행을 기준으로 먼저 채워나간다고 생각해보자.

1. 6개의 행 중 하나의 행에서 4개의 열에 X가 들어갈 수 있다. => 4가지

2. 5개의 행 중 하나의 행에서 3개의 열에 X가 들어갈 수 있다. => 3가지

3. 4개의 행 중 하나의 행에서 2개의 열에 X가 들어갈 수 있다. => 2가지

4. 3개의 행 중 하나의 행에서 1개의 열에 X가 들어갈 수 있다. => 1가지

5. 남은 2개의 행에는 모든 열에 X가 들어갈 수 있다. => $4\times4$가지

따라서 경우의 수는 $4!\times4^2$ 가지이다.

그런데 6개의 행 중에서 열이 중복되지 않는 행을 4개 선택해야하고, 그 경우는 $_6C_4$가지이다.

따라서 모든 경우의 수는 $_6C_4\times4!\times4^2 = \,_6P_4\times4^2$이다.