[백준] 성지키기

성 지키기

성의 크기와 경비원의 위치가 주어졌을 때, 모든 행과 모든 열에 적어도 한 명의 경비원이 있도록 추가로 필요한 최소한의 경비원 수를 구하는 문제입니다.

제한 사항

• 시간 제한: 2초
• 메모리 제한: 128MB
• 제출: 16721
• 정답: 6900
• 맞힌 사람: 5800
• 정답 비율: 43.126%

문제 링크

입력

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

출력

• 첫째 줄에 모든 행과 모든 열에 적어도 한 명의 경비원이 있도록 하기 위해 추가해야 하는 경비원의 최솟값을 출력합니다.

해결 전략

이 문제는 각 행과 각 열을 독립적으로 검사하여, 경비원이 한 명도 없는 행과 열의 수를 세어, 둘 중 더 큰 값이 추가로 필요한 최소한의 경비원 수가 됩니다. 이는 각 행과 각 열에 최소 한 명의 경비원이 배치되어야 하며, 한 명의 경비원을 추가함으로써 한 행과 한 열에 동시에 영향을 줄 수 있기 때문입니다.

코드 구조

public static void main(String[] args) {
  // Scanner 객체 생성: 사용자 입력을 받기 위함
  Scanner sc = new Scanner(System.in);

  // 성의 세로 크기 N과 가로 크기 M 입력 받기
  int N = sc.nextInt();  // 성의 세로 크기
  int M = sc.nextInt();  // 성의 가로 크기
  sc.nextLine();  // 다음 줄(상태 입력 시작점)으로 이동

  // 각 행과 각 열에 경비원이 있는지 여부를 저장할 배열
  boolean[] rowHasGuard = new boolean[N];  // 각 행에 경비원이 있는지 여부
  boolean[] colHasGuard = new boolean[M];  // 각 열에 경비원이 있는지 여부

  // 성의 상태 입력 받기 및 경비원 위치 파악
  for (int i = 0; i < N; i++) {
    String line = sc.nextLine();  // 성의 각 행 상태 입력 받기
    for (int j = 0; j < M; j++) {
      if (line.charAt(j) == 'X') {  // 해당 위치에 경비원이 있는 경우
        rowHasGuard[i] = true;  // 해당 행에는 경비원이 있다고 표시
        colHasGuard[j] = true;  // 해당 열에는 경비원이 있다고 표시
      }
    }
  }

  // 경비원이 없는 행과 열의 수 세기
  int rowsWithoutGuard = 0;  // 경비원이 없는 행의 수
  int colsWithoutGuard = 0;  // 경비원이 없는 열의 수

  for (boolean hasGuard : rowHasGuard) {
    if (!hasGuard) rowsWithoutGuard++;  // 경비원이 없는 행의 수 증가
  }

  for (boolean hasGuard : colHasGuard) {
    if (!hasGuard) colsWithoutGuard++;  // 경비원이 없는 열의 수 증가
  }

  // 추가로 필요한 경비원의 수는 경비원이 없는 행과 열 중 더 많은 수
  System.out.println(Math.max(rowsWithoutGuard, colsWithoutGuard));
}