백준 배열 돌리기 4 : 요소별로 나누면 어렵지 않다.

 오늘은 어떤 것을 배워볼까요? 시계처럼 x칸씩 회전하는 연산을 배워보겠습니다. 17406번 배열 돌리기 문제를 보겠습니다. 문제가 요구하는 것은 간단합니다. 그 중에서 가장 중요한 것은 rotate 연산입니다. 이것은 정사각형을 시계방향으로 1칸씩 돌린다는 의미입니다.

 

 

---

 문제가 다소 복잡하니, 분할해서 생각해 보도록 하겠습니다. 먼저, 돌아가는 단위를 기준으로 나누면, 기준점을 하나 잡을 수 있습니다. 이 기준점들을 먼저 잡아보겠습니다.

 

 

 먼저 회전 반경이 1이라고 해 보겠습니다. 0번만 있는 요소, 그리고 1 ~ 8까지 있는 요소 둘로 나눠보겠습니다. 그러면, 제가 보라색으로 칠한 것은 각각의 요소들의 기준점으로 볼 수 있습니다.

 

 

 그리고, 1번은 1 ~ 8은 하나의 요소로 볼 수 있습니다. 이들이 1칸씩 회전했다는 것을 구현하려면 어떻게 해야 할까요? 일단, 각 좌표별로 돌리는 순서를 매기는 방법을 생각해 볼 수 있습니다. 중심으로부터 1만큼 떨어졌다고 말할 수 있는, 보라색과 노란색으로 칠해져 있는 요소들을 생각해 보겠습니다. 즉, 중심점으로부터 x 방향으로 -1, y 방향으로 -1만큼 이동한 point는, 반경 1 요소의 기준점인데요. 여기에서 어떠한 조작을 해 보도록 하겠습니다.

 

 

 먼저 연두색으로 칠해진 것들을 보겠습니다. 이들은, 가로 방향으로 1만큼 이동하면 됩니다. 가로 방향으로 2만큼 이동하면, 3에 도착하게 됩니다. 다음에 4, 5는 어떨까요? 3을 기준으로 보면, 아랫쪽으로 이동하면 됩니다.

 

 

 3을 기준으로, 아랫쪽으로 1칸 이동하면 4, 1칸 더 이동하면 5가 됩니다. 그 다음에 방향이 또 바뀝니다. 그러면, 5를 기준점으로 잡고, 이동해 보도록 하겠습니다.

 

 

 5를 기준으로, 왼쪽으로 1칸씩 이동하면 된다는 것을 알 수 있어요. 즉, 가로 방향으로 -1만큼 이동하면 됩니다. 그 다음에는 어떤가요? 7을 기준으로 위로 올라가면 됩니다.

 

 

 그러면 어떻게 번호를 매겨야 할 지 알았으니, 이것을 먼저 코드로 옮겨보겠습니다.

 

 

---

 먼저, 오른쪽, 아래, 왼쪽, 윗 방향을 순서대로 저장한 방향 배열들과, 각 요소들을 시계 방향으로 돌린 좌표들을 저장한 배열인 con을 선언하겠습니다.

 

 

 각각 오른쪽, 아랫쪽, 왼쪽, 윗쪽을 저장한 방향 벡터들입니다. 이것은, 코딩 테스트에도 나오기도 하고, 그래프 탐색에서도 많이 나오니, 많이 풀어보시면서 익숙해 지시면 됩니다.

 

 

 다음에 rotate 함수는 중심점은 요소 0번에 속해 있습니다. 거리가 0이라고 제가 정의했기 때문이에요. 다음에 cx와 cy는 제가 말한 기준점을 의미합니다. 이것들은, 1요소, 2요소 3요소로 갈 수록, cx값과 cy값이 하나씩 줄어듭니다.

 

 

 69번째 줄 di는 방향을, t는 해당 방향으로 최대 몇 칸만큼 가고 방향을 바꿀 것인지를 나타냅니다. 2i만큼 가고 바꾼다는 것을 알 수 있는데요. 이 관계식은 2번 요소로 확장을 시켜 보면 크게 어렵지 않다는 것을 알 수 있습니다.

 

 

 그러면 (x,y)를 기준으로 반경이 r인 원을 만들어서 1칸씩 회전하겠다는 쿼리가 들어왔을 때, 각 요소별로 좌표를 얻어내는 것까지는 했습니다. 이것만 하면 무엇을 하나요? 1칸씩 이동을 시켜야 합니다. 이 작업을 간결하게 구현하기 위해서, 임시 배열 temp를 선언하겠습니다.

 

---

 temp를 선언했다고 해 봅시다. 그러면, 1칸씩 시계 방향으로 회전했을 때 어떻게 이동했나요?

 

 

 8, 1, 2, 3, 4, 5, 6, 7 순서로 오게 되었습니다. 기존에는 1, 2, 3, 4, 5, 6, 7, 8 순서로 되어 있었던 것이요.

 

 

 이전에 번호 매긴 순으로 저장했던 배열을 p라고 하고, 배열의 크기를 sz라고 합시다. 1회전 후에, c배열에 넘버링 한 것을 저장하려고 한다면, c[i]에는 p[i-1]이 들어가야 합니다. 그런데 i값이 0인 경우에는, sz-1이 들어가야 합니다. 사실 이는 (i+sz-1)%sz로 다시 적을수 있습니다.

 

 

 prev와 cur의 관계는 이해가 되실 거에요. 그리고 con[i][cur].x는 i번째 요소의 cur번째 x좌표를 의미합니다. 그러면 con[i][prev].x는 i번째 요소의 prev번째 x좌표를 의미할 겁니다. 회전하고 난 후의 cur번째 좌표는, 회전하기 전의 prev번째 좌표와 같습니다. 87번째 줄은, brr의 값을 토대로 회전한 결과를 저장하는 임시 배열에 저장하는 문장입니다.

 

 그리고, 임시 배열에 회전 결과물을 저장해 놓은 것을 반영해야 합니다. 이는 89번째 for 문에서 수행하고 있습니다.

 

 

 회전만 적절히 구현되었다면, 나머지 부분은 크게 어려운 것이 없습니다. next_permutation과 do while 조합을 쓰면서 모든 조합을 다 돌아보면서, 문제에서 구하라고 하는 것을 구하면 됩니다. 이것은 생각보다 자주 보이니, 연습을 해 두면 좋을 듯 싶습니다.