1exxn   1년 전

예제 입력 3

5 8
....XXXX
........
XX.X.XX.
........
........

인데

정답은 3이라고 합니다

근데 저거를

....XXXX
..XX....
XX.X.XX.
........
........

이런식으로 2개만 두면 다 막히는거 아닌가요?

lcr7324   1년 전

"영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다."

말씀하신대로 두면 4행과 5행이 막히지 않습니다.

1exxn   1년 전

아 그렇군요 그러면

....XXXX
..X.....
XX.X.XX.
.......X
........ <-여긴 아무나

가 답이 되겟네요

이걸 어케 풀죠

브론즈 1이라고 해서 풀어볼려 했는데

wizardrabbit   1년 전

풀이를 설명하되, 단계별로 힌트를 적는 식으로 적어볼게요. 막힐 때마다 조금씩 공개해서 보시면 좋을 것 같아요. 스포일러 방지를 위해 빈 줄을 좀 넣을게요! 아래로 스크롤해주세요!

힌트 1

모든 행과 열에 한 명 이상의 경비원이 있어야 한다는 뜻은, 비어있는 행과 비어있는 열의 개수가 모두 $0$개여야 함을 의미해요. 비어있는 행과 비어있는 열의 개수를 세어 개수를 알 수 있다면 문제 해결에 도움이 될 수 있을 거에요.

힌트 2

경비병을 한 명 배치했을 때 비어있는 행을 없애기 위해 배치한다면 비어있는 행의 개수는 반드시 $1$ 감소할 것이고, 비어있는 열을 없애기 위해 배치한다면 비어있는 열의 개수는 반드시 $1$ 감소할 거에요.

힌트 3

비어있는 행을 없애기 위해 배치한 경비병이 비어있는 열 중 하나를 동시에 없앨 수 있을까요? 비어있는 행과 비어 있는 열을 합쳐 십자가로 생각한다면요?

힌트 4

비어있는 행 중 하나를 $r$번째 행이라고 하고, 비어있는 열 중 하나를 $c$번째 열이라고 하면, $(r, c)$ 자리는 항상 비어있을 것이고, 여기에 경비병을 배치하면 비어있는 행과 열의 수를 각각 $1$씩 확실하게 감소시킬 수 있어요. 행과 열의 개수를 각각 $2$씩 감소시키는 것은 불가능하니 이것이 최선의 전략일 거에요.

힌트 5

따라서, 비어있는 행이 $r$개, 비어있는 행이 $c$개라면 한 명의 경비병을 배치했을 때 반드시 $r$, $c$를 $1$씩 감소시킬 수 있으니 답은 $r$, $c$ 중 더 큰 값이 돼요. 이중 반복문 등을 이용해 구현할 수 있어요.

1exxn   1년 전

힌트 4까지 보고 푸는데 성공햇습니다. 힌트 5를 안봐서 그런지 행 개수와 열 개수 대신 비어 있는 행, 열의 위치를 구해 비어 있는 행과 열을 동시에 pop하고 아니면 행 또는 열을 pop해서 count를 올리는 식으로 했는데 더 간단한 방법이 있었네요

댓글을 작성하려면 로그인해야 합니다.