성 지키기 [1236]

성 지키기 [1236]

백준 - https://www.acmicpc.net/problem/1236

1236번: 성 지키기

문제

• 영식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다.
• 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.
• 성의 크기와 경비원이 어디있는지 주어진다.
• 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오.

 

---

입력

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

출력

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

예시

 

---

풀이과정

• 핵심은 가로마다 세로마다 필요한 경비원 수 중 큰값이 답이라는 것
• 가로열끼리는 리스트의 원소들로 이루어져있어 not in 을 이용해서 'X' 를 걸렀다.
  • 'X' 가 없다면 필요 경비수 +1
• 세로열끼리는 리스트의 원소로 이루어져있는것이 아니다!
  • 2차원 배열을 전부 순회하여 세로 순서로 비교했다.
  • 'X' 가 있다면 최대 경비수 -1
• 세로 가로 경비수 중 큰 값을 출력

 

---

느낀점

• input 받는거 나만 어려운건지 모르겟다.

• 2차원 배열을 쓰는것에 익숙하지 않아 어려웠다.

• 문제 자체로도 난이도가 있었다고 생각한다.