문제 설명

영식이는 직사각형 모양의 성을 가지고 있다.
성의 각 칸에는 경비원이 있거나(X) 없을 수 있다(.).

영식이는 다음 조건을 만족하도록 성을 지키고 싶다.

모든 행과 모든 열에 최소 한 명 이상의 경비원이 존재해야 한다.

현재 성의 상태가 주어졌을 때
추가해야 하는 경비원의 최소 개수를 구하는 문제이다.

---

입력

첫째 줄

N M

• N : 성의 세로 크기
• M : 성의 가로 크기

둘째 줄부터 N개의 줄

. 또는 X

• . : 빈 칸
• X : 경비원이 있는 칸

조건

1 ≤ N, M ≤ 50

---

출력

조건을 만족하도록 추가해야 하는 최소 경비원의 수를 출력한다.

---

입력 예시

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

출력 예시

4

---

문제 해결 아이디어

이 문제의 핵심은 다음이다.

경비원이 없는 행의 개수
경비원이 없는 열의 개수

를 각각 구하는 것이다.

예를 들어

....
....
....
....

이 경우

• 행 : 4개 모두 경비원 없음
• 열 : 4개 모두 경비원 없음

즉

행 필요 개수 = 4
열 필요 개수 = 4

여기서 필요한 경비원의 최소 개수는

max(행 필요 개수, 열 필요 개수)

이다.

---

왜 max를 사용하는가

경비원 한 명은

행 1개 + 열 1개

를 동시에 만족시킬 수 있기 때문이다.

예를 들어

행 부족 = 3
열 부족 = 1

이라면

3

명의 경비원이 필요하다.

따라서

max(행 부족 개수, 열 부족 개수)

가 최소 경비원 수가 된다.

---

내가 작성한 풀이

행과 열에 경비원이 있는지 여부를 배열로 저장한 뒤
경비원이 없는 행과 열의 개수를 계산했다.

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int cal = sc.nextInt();
        int row = sc.nextInt();
        sc.nextLine();

        int[] calX = new int[cal];
        int[] rowX = new int[row];
        char[][] arr = new char[cal][row];

        int calResult = cal;
        int rowResult = row;

        for (int i = 0; i < cal; i++) {
            arr[i] = sc.nextLine().toCharArray();
        }

        for (int i = 0; i < cal; i++) {
            for (int j = 0; j < row; j++) {
                if (arr[i][j] == 'X') {
                    calX[i] = 1;
                    rowX[j] = 1;
                }
            }
        }

        for (int i = 0; i < cal; i++) {
            if (calX[i] == 1) {
                calResult--;
            }
        }

        for (int i = 0; i < row; i++) {
            if (rowX[i] == 1) {
                rowResult--;
            }
        }

        System.out.println(Math.max(calResult, rowResult));
    }
}

---

강의 풀이

강의에서는 행과 열에 경비원이 존재하는지를
boolean 배열을 사용하여 처리했다.

코드

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];

        for (int i = 0; i < N; i++)
            map[i] = sc.next().toCharArray();

        boolean[] rowExist = new boolean[N];
        boolean[] colExist = new boolean[M];

        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                if (map[i][j] == 'X') {
                    rowExist[i] = true;
                    colExist[j] = true;
                }

        int rowNeedCount = N;
        int colNeedCount = M;

        for (int i = 0; i < N; i++)
            if (rowExist[i]) rowNeedCount--;

        for (int i = 0; i < M; i++)
            if (colExist[i]) colNeedCount--;

        System.out.println(Math.max(rowNeedCount, colNeedCount));
    }
}

---

두 풀이 방식 비교

방식	특징
int 배열 사용	0과 1로 경비원 여부 표현
boolean 배열 사용	true / false로 표현

두 방식 모두

행에 경비원이 있는지
열에 경비원이 있는지

를 저장한다는 점에서 로직은 동일하다.

---

시간 복잡도

성의 모든 칸을 한 번 확인한다.

O(N × M)

최대 크기

50 × 50 = 2500

이므로 매우 빠르게 실행된다.

---

핵심 개념

이 문제에서 중요한 개념은 다음과 같다.

1. 행에 경비원이 존재하는지 확인
2. 열에 경비원이 존재하는지 확인
3. 경비원이 없는 행과 열의 개수 계산
4. 최종 결과

max(행 부족 개수, 열 부족 개수)

---

정리

이 문제는 처음 보면 경비원을 어디에 배치해야 할지 고민하게 되지만,
실제로는 행과 열에 경비원이 존재하는지만 확인하면 되는 문제였다.

각 행과 각 열에 경비원이 있는지를 체크한 뒤
경비원이 없는 행과 열의 개수를 구하고

max(행 부족 개수, 열 부족 개수)

를 출력하면 문제를 해결할 수 있다.