[JAVA] 백준 1236 - 성 지키기

문제

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

 

입력

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

 

출력

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

 

입출력 예제

 

알고리즘❓ 풀어내기❗️

1. 모든 행과 열에 경비원이 최소 한 명씩 있어야 할 때, 추가로 필요한 경비원의 최소 수를 구하는 문제다.
2. 각 행/열에 대해 경비원이 있는지 확인한다.
3. 보호받지 못하는 행/열의 개수를 구한다.
4. 둘 중 큰 값이 추가로 필요한 경비원의 최소 수라는 규칙을 파악하면 문제를 쉽게 풀 수 있다.

🧑🏻‍💻코드 리뷰 - (1)

import java.util.Scanner;

public 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();
        }

        int existRowCount = 0;
        for (int i = 0; i < N; i++) {
            boolean exist = false;
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 'X') {
                    exist = true;
                    break;
                }
            }
            if (exist) existRowCount++;
        }

        int existColCount = 0;
        for (int j = 0; j < M; j++) {
            boolean exist = false;
            for (int i = 0; i < N; i++) {
                if (map[i][j] == 'X') {
                    exist = true;
                    break;
                }
            }
            if (exist) existColCount++;
        }

        int needRowCount = N - existRowCount;
        int needColCount = M - existColCount;

        System.out.println(Math.max(needRowCount, needColCount));
    }
}

▶ 첫번째 for 문 : for루프를 사용하여 N개의 행에 대한 입력을 받는다. toCharArray() 메서드를 사용하여 입력된 문자열을 char 배열로 변환한다. 변환된 char 배열을 map 배열의 i 번째 행에 저장한다. 이로써 N개의 행, M개의 열에 해당하는 2차원 배열에 입력된 문자열이 저장된다.
▶ 두번째 for 문 : 경비원이 존재하는지 여부를 알기 위한 exist 변수를 선언하고 행을 순회하며 X인 요소를 만나면 exist에 true를 대입한 뒤 existRowCount를 1씩 증가시킨다. 
▶ 세번째 for 문 : 경비원이 존재하는지 여부를 알기 위한 exist 변수를 선언하고 열을 순회하며 X인 요소를 만나면 exist에 true를 대입한 뒤 existColCount를 1씩 증가시킨다. 
▶ int needRowCount : 전체 행의 개수인 N에 위에서 구한 existRowCount를 빼면 경비원이 필요한 행의 개수를 구할 수 있다. needColCount도 마찬가지다.
▶ Math.max(needRowCount, needColCount) : 둘 중 큰 값을 구한다.
 

🧑🏻‍💻코드 리뷰 - (2)

import java.util.Scanner;

public 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));
    }
}

▶ 각 행, 열의 크기에 맞게 boolean타입 배열을 선언해 준 후 배열을 순회하며 'X'를 만나면 true를 대입해 준다.
▶ 객 행, 열의 배열을 순회하며 배열의 원소가 true이면 needCount에 -1을 해준다.