[Baekjoon] 1236번 : 성 지키기

1. 문제

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

• 탐색 문제

// 문제
영식이는 직사각형 모양의 성을 가지고 있다.
성의 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

2. 핵심 아이디어

• 모든 행과 모든 열에 한 명 이상의 경비원이 있어야 함
• 행 기준, 열 기준으로 필요한 경비원의 수를 각각 계산하여 더 큰 수 출력

3. Python 문제풀이

import sys

n, m = map(int, sys.stdin.readline().split())
arr = []

for _ in range(n) :
  arr.append(sys.stdin.readline())

row = [0] * n
column = [0] * m

for i in range(n) :
  for j in range(m) :
    if arr[i][j] == 'X' :
      row[i] = 1
      column[j] = 1

row_count = 0
for i in range(n) :
  if row[i] == 0 :
    row_count += 1

column_count = 0
for j in range(m) :
  if column[j] == 0 :
    column_count += 1

print(max(row_count, column_count))

4. Java 문제풀이

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    char[][] map = new char[n][m];
    boolean[] row = new boolean[n];
    boolean[] col = new boolean[m];
    int c = 0;
    int r = 0;

    for (int i = 0; i < n; i++) {
      map[i] = sc.next().toCharArray();
      for (int j = 0; j < m; j++) {
        if (map[i][j] == 'X') {
          col[j] = true;
          row[i] = true;
        }
      }
    }

    for (int i = 0; i < n; i++) {
      if (!row[i]) {
        ++r;
      }
    }
    for (int i = 0; i < m; i++) {
      if (!col[i]) {
        ++c;
      }
    }
    System.out.println(c > r ? c : r);
  }
}