배열_백준_1236_성지키기

1236번: 성 지키기

문제 해석

영식이는 직사각형 모양의 성을 가지고있고 경비원을 알맞게 배치해서 영식이를 만족시켜야함

영식이를 만족시키는 방법은 경비원을 모든 행과 열에 경비원을 최소 한명씩은 배치 시켜야함

접근

예제1에서는 모든 행과 열에 경비원이 있어야함. 즉 대각선에 있으면 됨.(따로따로 배치해도 되긴함)

단, 모든 행과 열을 커버하려면 현재 경비원이 있는 행과 열을 제외하고 경비원이 들어가야함 이말은 색칠을 싹싹 하고 남은 칸에 경비원을 배치해야함(표를 그려보면 된다)

• 각 행과 열에 경비원이 있나?
• 보호받지 못하는 행열의 개수를 구한다
• 둘 중 큰 값을 출력힌다.

풀이

1. 행과 열을 따로따로 계산한 버전

package learnString;

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

        // 1. 각 행/열에 대해 경비원이 있는지 확인힌다.
        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 i = 0; i < M; i++) {
            boolean exist = false;
            for (int j = 0; j < N; j++) {
                if (map[j][i] == 'X') {
                    exist = true;
                    break;
                }
                if (exist) {
                    existColCount++;
                }
            }
        }

        // 2. 보호받지 못하는 행/열의 개수를 구한다.
        int needRowCount = N - existRowCount;
        int needColCount = M - existColCount;

        // 3. 둘 중 큰 값을 출력한다.
        System.out.println(Math.max(needRowCount, needColCount));

    }
}

2. 행과 열을 한번에 체크해보기

package learnString;

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

        // 1. 각 행/열에 대해 경비원이 있는지 확인힌다.
        boolean[] existRow = new boolean[N];
        boolean[] existCol = new boolean[M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 'X') {
                    existRow[i] = true;
                    existCol[j] = true;
                }
            }
        }

        // 2. 보호받지 못하는 행/열의 개수를 구한다.
        int needRowCount = N;
        int needColCount = M;
        // 전체 행에서 경비원이 있는 행을 빼주면 없는 행만 남는다.
        for (int i = 0; i < N; i++) {
            if (existRow[i]) {
                needRowCount--;
            }
        }
        for (int i = 0; i < M; i++) {
            if (existCol[i]) {
                needColCount--;
            }
        }

        // 3. 둘 중 큰 값을 출력한다.
        System.out.println(Math.max(needRowCount, needColCount));

    }
}