[BOJ][1236번] 성 지키기

안녕하세요 Dibrary입니다.

문제를 풀 때 알고리즘을 잘 알고 있는 것도 중요하지만, 아이디어의 중요성? 을 다시 한 번 깨닫게 된 문제가 있어서 가져와봤습니다.

1236번: 성 지키기

 

 

---

딱 보면 엄청 간단해 보이죠. 네 알고리즘 풀이에 어느정도 익숙한 분이라면 바로 풀 아이디어가 떠오르실 겁니다. (전 아니지만요... ㅠ.ㅜ)

 

제가 생각한 아이디어는 아래와 같습니다.

1. 모든 점을 지나면서 행과 열을 확인하고, 둘 중에 X가 하나도 없는 지점에서 X를 추가한다.
2. 모든 점을 어떻게 지나갈까? for문으로 한 번 돌려보자.
3. 그 다음에 BFS로도 구현 해 보자.

근데, 이렇게 하니까 틀렸습니다. 왜일까요? 

이 문제에서 원하는 답은 '최솟값' 입니다.

문제에서의 예제 4번을 보죠.

이랬던 입력 배열이

이렇게 바뀝니다.

아니 새롭게 X 4개를 찍어버렸네요. 답은 3개인데요. 그냥 눈으로 보아도 3개만 있으면 되는데 말이죠..

 

---

그래서 생각을 하기 시작했습니다.

1. 그럼 행, 열이 하나도 안 겹치는 포인트만을 찾아서 검사하면 되지 않을까?
2. 대각선으로 내려가면서 체크해보자.

근데, 이 문제에서 주어진 사각형은 항상 정사각형이 아니라는 점이죠...

 

 

그 다음에 발상을 바꾼게 정답이 되었습니다.

1. 그러면 모든 점을 돌아다니면서 행,열에 단 하나도 X가 없는 부분에 X표시를 먼저 해 둔 후에
2. 그 다음에 다시 모든 점을 돌아다니면서 행이나 열에 X가 없는 경우 X표시를 하고 갯수를 세자

결국 1번을 생각해 내야 '최소값'에 가까워질 수 있겠다 이렇게 생각했습니다.

코드는 아래와 같습니다.

중복되는 부분이 많기 때문에 중복되는 부분만 별도로 분리하면 실행 결과는 같고 보기에 깔끔하지 않을까 싶네요.