백준 1236 성 지키기 JAVA 풀이 (구현, 그리디)

🔗 문제 링크

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

---

📌 문제 개요

N x M 크기의 성이 주어진다.
각 칸에는:

• 'X' : 경비원이 있음
• '.' : 경비원이 없음

조건:

• 모든 행과 모든 열에는 최소 1명의 경비원이 있어야 한다
• 추가로 배치해야 하는 최소 경비원 수를 구하는 문제

---

📌 접근 방법

이 문제는 단순 구현 + 아이디어 문제

1. 전체 맵을 저장
2. 각 행을 순회하면서
   • 경비원이 없는 행 개수 체크
3. 각 열을 순회하면서
   • 경비원이 없는 열 개수 체크
4. 두 값 중 큰 값을 출력

---

📌 핵심 아이디어

핵심은 이 한 줄이다 

• 결과 = max(경비원 없는 행 수, 경비원 없는 열 수)

 

왜 max를 쓰는가?

경비원 1명은 한 위치에 배치되면 행 + 열을 동시에 커버 가능

 

즉,

• 행이 부족한 수: 3
• 열이 부족한 수: 2

최소 배치 수는 3

 

왜냐하면:

• 더 부족한 쪽을 기준으로 채워야
• 모든 조건을 만족할 수 있기 때문

 

예시

.X.
...
..X

 

행 기준

• 0번 행 → 있음
• 1번 행 → 없음
• 2번 행 → 있음

rowCount = 1

 

열 기준

• 0번 열 → 없음
• 1번 열 → 있음
• 2번 열 → 있음

colCount = 1

 

결과: max(1, 1) = 1

 

---

📌 전체 코드

package no_1236;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class No1236 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        char[][] map = new char[N][M];

        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }

        int rowCount = 0;
        int colCount = 0;

        // 행 검사
        for (int i = 0; i < N; i++) {
            boolean hasGuard = false;
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 'X') {
                    hasGuard = true;
                    break;
                }
            }
            if (!hasGuard) rowCount++;
        }

        // 열 검사
        for (int j = 0; j < M; j++) {
            boolean hasGuard = false;
            for (int i = 0; i < N; i++) {
                if (map[i][j] == 'X') {
                    hasGuard = true;
                    break;
                }
            }
            if (!hasGuard) colCount++;
        }

        System.out.println(Math.max(rowCount, colCount));
    }
}

---

📄 정리

• 행과 열을 각각 따로 검사하는 문제
• 핵심은 “동시에 커버 가능”이라는 점