[BOJ] 백준 15925 욱제는 정치쟁이야!!

문제 링크

https://www.acmicpc.net/problem/15925

사용 여부가 1이든 0이든 풀이는 같으니 0이라고 가정하고, N크기가 어떻든 풀이는 같으니 N = 5라고 가정하자.

N*N 정사각형에서 한 행을 보자.

이런 경우는 전부 0으로 만들 수 있으므로 한행을 전부 0으로 만든다.

이런 경우 행의 차원에서는 1을 0으로 바꿀 방법이 없다.

그럼 저 1은 누가 0으로 바꿀 수 있을까? 바로 해당 칸의 열에서 바꿀 수 있다. 

마찬가지로 한 열을 봤을 때

  

이런 경우에 저 1들은 해당 칸의 행에서만 0으로 바꿀 수 있다.

행 차원에서 모든 행을 먼저 탐색하고, 그 후 모든 열을 탐색하면 행의 차원에서만 봤을 때 바꾸지 못했던 1들의 값이 결정될테고, 다시 행을 훑어보면서 한 행을 0으로 바꿀지 말지 결정할 수 있다.

행 - 열 - 행 의 순서로 보면 행의 값들을 결정할 수 있으니 반대로 열 - 행 - 열의 순서로 탐색하면 열의 값들을 결정할 수 있다. 

따라서 행 - 열 - 행 - 열 의 순서로 탐색하면 모든 칸에 대해 값을 결정할 수 있다.

물론 열 - 행 - 열 - 행의 순서로 봐도 같은 답을 구할 수 있다.

정답 코드

질문, 피드백 환영합니다.