[백준] 성 지키기 (구현, Java)

 

문제설명

입력 & 출력

나의 풀이

 

이번 문제는 N x M 크기의 성이 주어지고, 성의 각 칸에는 경비가 배치된 경우 'X'가 표시됩니다.

 

주어진 성에 행과 열마다 최소 한 명의 경비가 배치되도록 해야 합니다. 따라서, 행과 열 중에서 경비가 배치되지 않은 행과 열의 수를 구하고, 그 중 더 큰 값을 출력하는 것이 목표입니다.

 

먼저 입력조건에 따라 입력을 받아주고, toCharArray()메서드로 문자열을 char형 배열로 저장합니다.

이 때 2중 for문을 사용하여 위 그림과 같이 행(row)과 열(column)을 순회해줘야 합니다. 위 그림의 번호대로 각 행과 열을 순회하고 각 행과 열의 필요한 경비 수 를 구해줍니다.

 

그리고 각 경비원이 담당할 수 있는 공간이 행 또는 열 중 하나에만 추가 배치된다고 가정했을 때, 두 값 중 더 큰 값이 최솟값이 됩니다. 행이나 열 어느 한쪽에만 추가 경비원을 배치해도 모든 빈 공간을 채울 수 있기 때문입니다.