한 번 고쳐서 제출해 봐야겠다.
그리고 다시 보니, 한 칸을 결정할 때, 비숍을 놓기로 결정하면 대각선 방향의 칸에는 비숍을 놓을 수 없게 되는데, 이 것을 어떻게 체크하냐면 만약 (r, c)에 놓는다 치면, x+y == r+c이거나 x-y==r-c인 곳은 놓을 수 없는 대각선을 의미하게 된다.
구현이 간단하지는 않다. 조금 까다롭지만 예제로 테스트 해보고 제출했는데 또 시간초과..
이렇게 하는 방법도 결국은 최대 2의 100제곱이라 그런 것인가...
문득 든 생각이 그렇다면 memoization을 활용해 보는 것... 음 근데 그렇다면 체스판의 상태에 따라 다르게 결정되므로 체스판의 상태에 따라 memoization을 해줘야 하는데, 상태dp를 하듯이 state를 배열로 판별하면 ...칸이 최대 100칸이라 너무 크다. 음...
--------------------------------------------------------------------------------
백트래킹을 어떻게 해야 시간을 단축시킬 수 있을까?
질문 검색을 보다가 힌트를 얻었다. nqueen문제는 한 행씩 한 열씩 제하면서 가면 되듯이, 이 비숍문제는 대각선 한 행이 아닌 한 번에 한 대각선이다!
오... 일단 대각선/을 차례로 보면서 대각선/에 있는 칸에 bishop을 놓을지 말지 결정하고, 그에 따라 반대 대각선\도 체크하면서 나간다. (그리고 전체 칸 n*n을 체크할 필요 없이 어떤 대각선에는 놓을 수 없다... 이런 식으로 대각선별로 체크하면 된다.)
대각선을 체크하기 위한 배열을 쓰려 하는데, 각 대각선에 해당하는 index를 어떻게 맞출까 고민이다. 각 칸은 행과 열로 나타낼 수 있는데, 어떤 대각선에 속하는지 판별하기가 쉽지 않다.
일단 반대 대각선\에 대해 보면, (0, n-1)부터 시작하는 대각선부터 (n-1, 0)부터 시작하는 대각선까지 2n-1개의 대각선이 존재한다.
특징을 보면
(0, n-1)부터 시작하는 대각선상의 칸 (x, y)는 x-y값이 -(n-1) 이고,
쉬운 이해를 위해, (0, 3)부터 시작하는 대각선 상의 칸 (x, y)에 대해 x-y값은 0-3이다.
즉 반대 방향 대각선\의 경우 각 대각선에 존재하는칸의 행-열 값이 각 대각선마다 고유하다. 그런데 음수이면 배열의 index로 쓸 수 없으므로 n-1을 더해준다.
그럼 (0, n-1)부터 시작하는 대각선의 index는 0이 되고, (0, n-2) -> index1,....., (n-1, 0) 에서 시작하는 대각선의 index는 n-1이 된다. 이렇게 반대 방향 대각선\에 대해서 index를 0부터 n-1까지로 나타낼 수 있다.
그리고 대각선/단위로 볼 때, 비숍을 한 대각선/에 하나만 놓거나 아예 안 놓거나 둘 중 하나이다. 그래서 아예 그 대각선/에는 놓지 않는 경우를 처리해주고, 한 칸에만 놓는 경우들을 처리해주면 된다.
그리고 backtracking함수의 parameter로 r, c를 보내는데, 이 행, 열 정보는 각 대각선/의 시작점을 의미한다.
그런데도 시간초과를 받았다. 시간 복잡도에 대해 생각해보니 각 대각선 별로 한 칸씩 선택하는 경우와 선택하지 않는 경우에 대해 다 해보는 것이므로 O(2*3*....*(n-1)*n*(n-1)*...*2)... 이런 식이 되지 않을까? n이 10인 경우에는 O(10! * 9!) 정도..? 물론 여러 조건때문에 중간 중간 좀 더 시간이 줄긴 하겠지만 시간 초과가 날만도 해보인다.
---------------------------
결국 질문 게시판을 보고 어떻게 풀어야할지 알게 되었다.
어떤 분의 코드와 유카리코님의 답변 을 보면,
내가 푼 방식과 비슷하다. 그런데 차이가 있다면 바로 마지막 줄, "위 코드는 인접한 대각선끼리는 독립적이라는 사실을 이용하여 반으로 쪼개어 더해준 것으로 최적화를 수행한 것 같습니다."
처음에는 무슨 말인지 이해가 안 됐지만 다른 질문글의 답변을 떠올려보고, 게시글의 코드에서 f(0)+f(1)을 답으로 출력하는 것을 보고 깨달음을 얻었다!
참조가 된 답변
체스판을 그려놓고 보면, 비숍이 흰 칸에 놓이면 나머지 칸에 대해서 영향을 줄 때, 오직 나머지 흰 칸들에 대해서만 영향을 준다. 마찬가지로 검은 칸에 놓이면 나머지 검은 칸에 대해서만 영향을 준다! 즉, 인접한 대각선끼리 독립적이라는 말은 인접한 대각선끼리는 색깔이 다르고, 흰 대각선은 흰 대각선끼리만 영향을 주고, 검은 대각선은 검은 대각선끼리만 영향을 끼치므로 흰 대각선, 검은 대각선 부분을 나눠서 비숍을 놓을 수 있는 개수를 구해서 합치는 방법으로 구할 수 있다. 그리고 이렇게 하면 반으로 나눠서 하는 것이기 때문에 시간 복잡도는 n이 10인 경우에, 그냥 나누지 않고 다 볼때의 O(10! * 9!) 에서 O(10! + 9!)로... 엄청나게 감소하게 된다!!!
검은 칸으로만(검은 대각선으로만) 구성된 부분에는 비숍을 어디에 놓든지 간에 흰 칸으로 구성된 부분에 영향을 끼치지 않기 때문이다! (반대로 흰 칸도 마찬가지...)
참고할 만한 것으로 대각선/도 index로 나타낼 수 있다. 대각선/의 경우는 편하다. 그냥 r+c만 하면 된다. 그리고 대각선을 한 칸 건너뛰는 것을 구현하려면 대각선/도 index로 나타내서 하는 것이 더 편한 것 같다. 그리고 index로 나타낼 경우 최대 2*n-1개라는 것도 주의!!
그리고 또 하나, 나는 원래 대각선에 아무 것도 안 놓는 경우도 생각했는데, 놓을 수 있으면 꼭 놓아야 할 것 같다. 앞에 놓든, 뒤에 놓든 그 대각선에는 하나의 비숍만 놓을 수 있고, 각 대각선당 한 개씩 놓아져야 한다. 그리고 한 대각선에 놓는다고 해서 같은 방향의 다른 대각선에 놓을 수 없게 되는 것도 아니고, 또한 뒤에 나오는 대각선에서의 칸은 놓을 수 없는 칸일 수도 있으므로 앞에서 놓을 수 있는 대각선과 놓을 수 있는 칸이 나온다면 미리미리 놓아야 최대를 구할 수 있을 것이다. 그리고 놓을 수 있는데도 아예 안놓고 넘어가는 경우에서 놓고 넘어가는 경우보다 더 큰 값이 나올 수 없을 것 같다. 일단 제출은 아무것도 안 놓는 경우를 포함하는 것도 해보고 그냥 무조건 하나씩 놓는 경우도 해봐야겠다.
-> 예상외로 바로 예제에서부터 답이 안 나와서.. 왜인가 봤더니... 이 예제에서 보면 처음 입력으로 주어질 때, 한 대각선이 비숍을 아예 놓을 수 없는 칸들로만 이루어져 있다. 그렇기 때문에 만약 아무것도 놓지 않는 조건을 빼면 그 대각선에서 끝나버리고 탐색을 안하기 때문에 최대값이 안 나온다... 내가 생각한 것을 실행하려면 아무것도 놓지 않는 조건을 빼는 대신 한 칸씩 고르는 while문 안에서 아무 것도 골라지지 않은 경우에 다음 대각선을 탐색하도록 추가하면 될 것 같다. 결국 AC를 받았다!!
-> 그리고 그냥 안 놓고 넘어가는 경우를 넣어봤더니 시간이 더 오래 걸린다. 0ms에서 8ms로 증가했다. 역시 굳이 할 필요 없는 경우까지 탐색하기 때문인 것 같다.
좋은 문제같다. 그리고 내가 시간 복잡도를 맞게 계산했는지는 모르겠지만 체스판과 비숍의 성질을 이용해서 반으로 나눠 푸는 방식으로 시간복잡도를 확 줄일 수 있다는 것은 사실이다.
아 그리고, 질문 게시판의 답변에 의하면 이분매칭, 최대유량 알고리즘으로도 풀 수 있다고 한다. 이참에 네트워크 플로우를 복습해서 이 문제도 네트워크 플로우로 풀어 봐야겠다.
댓글 없음:
댓글 쓰기