백준 배열 돌리기 5 : 전략적인 브루트 포스로 풀어봅시다.

 배열 돌리기 5는 solved 난이도로 골드 1인 문제입니다. 200만개의 쿼리를 브루트 포스하게 실행시키면, 시간초과가 나는 것은 당연해 보입니다. 높이가 100, 너비가 100인 배열을 어떻게 압축을 시키면 좋을까요?

 

 

---

 문제가 되는 것은 5번, 6번임을 알 수 있습니다. 가로로 반, 세로로 반을 나눠서 처리해야 하기 때문입니다. 사실 그것만 없었다면, 그냥 시점만 이동해서 풀 수 있었을 겁니다. 일단, 제 풀이는 브루트 포스입니다. 그런데, 100 by 100 전체를 브루트 포스를 하지 않습니다. 데이터를 압축하는 것이 목표입니다. 어떻게 잘 압축을 할까요? 배열 S가 아래와 같이 있다고 해 보겠습니다. 

 

 5, 6번 연산 때문에 이렇게 나누었다는 것을 눈치채셨을 겁니다. 이 4개의 영역 중에, 모서리 부분 4개만 가지고 올 겁니다. ps 문제를 푸실 때, 도움이 될 만한 팁 중 하나는 극단적인 케이스를 들고 오면 풀리는 경우가 많다입니다. 이 문제도 예외가 아닙니다. 이 전략이 합당할까요?

 

 5, 6번 연산이 복잡해 보입니다만, 핵심은 덩어리 4개로 나눠서 덩어리 별로 회전시키겠다는 겁니다. 5번 연산을 하면 아래와 같이 바뀝니다.

 

 

 여기서, 진한 부분만 가지고 있으면 원래 배열로 복원이 가능할까요? 네. 왼쪽 위를 보았을 때, 가로 방향은 2,0에서 2,1로 가는 방향이고, 세로 방향은 2,0에서 3,0으로 가는 방향임을 알 수 있어요.

 

 

 반대로 돌리면 어떨까요? 왼쪽 위 사각형의 가로 방향은 0,2에서 0,3으로 가고 있고, 세로 방향은 0,2에서 1,2로 가고 있습니다.

 

 

---

 S 배열에 1번 연산을 수행하였습니다.

 

 

 모서리 4개에 영역 4개, 16개의 정보만 가지고 복원할 수 있음을 알 수 있습니다. 왼쪽 위 정사각형의 경우에, 세로 방향으로 채워지는 것은 (3,0)에서 (2,0)으로 향하는 방향일 거고, 가로 방향으로 채워지는 것은 (3,0)에서 (3,1) 방향으로 향하는 방향일 겁니다. 2번 연산은 어떨까요? 이것은 좌우 반전입니다.

 

 

 모서리만 알고 있는 상태입니다. 방향을 추론할 수 있나요? 네. 왼쪽 위 사각형을 보았을 때 가로 방향은 0,3에서 0,2로 가는 방향이고, 세로 방향은 0,3에서 1,3으로 가는 방향이다. 라는 것을 끌어낼 수 있어요. 회전은 어떨까요?

 

 

 S 배열에 3번 연산을 적용한 후 모습입니다. 왼쪽 위 사각형을 보면, 방향을 추론할 수 있습니다. 가로 방향은 3,0에서 2,0으로 가고 있고, 세로 방향은 3,0에서 3,1로 가고 있음을 알 수 있어요. 복원 가능합니다. 4번 연산은 어떨까요? 4번은 3번 연산을 3번 하면 됩니다. 16개의 정보로 압축해도 상관 없음을 알 수 있습니다.

 

 

 혹은 이렇게 그림을 그려 보시고, 화살표가 어떻게 변하는지 시뮬레이션 돌려봐도 됩니다.

 

 

 예를 들어, 3번 연산을 수행한 후에는 위와 같이 변하고, 여기서 좌우 반전을 시켰다면, 아래와 같이 변할 겁니다.

 

 

  대충 맞아 들어가네요.

 

---

 그러면, 이 16개를 잘 돌리고 비벼야 한다는 것은 알겠습니다. 구축은 어떻게 하고, 연산을 하고 나서 복원은 어떻게 해야 할까요? 먼저 구축부터 봅시다.

 

 

 코너 16개만 짚는데요. x축은 0, n/2-1, n/2, n-1 순이고, y축은 0, m/2-1, m/2, m-1 순입니다. 이 값들을 4 by 4 배열에 차례대로 넣어서 관리하는 것이 편합니다. 1번부터 6번 연산이 들어오면, 4 by 4 배열만 잘 돌려주면 됩니다. 덩어리별로 돌리는 것 손으로 돌려봐도 되고, 배열 돌리기 6 문제를 푸셔도 됩니다. 하튼 brr[0][0]부터 brr[3][3]까지는 실제 모서리들의 위치 정보를 넣습니다.

 

 복원은 어떻게 할까요? 시작점과 방향을 알면, 복원할 수 있습니다.

 

 

 방향은 x와 y 방향이 있는데요. x축으로 -6만큼 가고, y축으로 0만큼 간다. 이런 방향이 있을 수 있습니다. 각 모서리 별로 방향을 따질 때요. 그런데, 실제로 채울 때에는 1칸 단위로 움직일 겁니다. 따라서, 정규화를 시켜 주어야 하는데요. 들어오는 값이 음수이면 -1로, 양수이면 1로 정규화를 해 줍니다. 익숙해 져야 하는 용어 중 하나입니다.

 

 ps를 하면서도 많이 나오는 트릭일 수 있으니 익혀두시면 좋습니다.

 

 

 각 직사각형 별로 가로 방향, 세로 방향을 계산한 후에는, 단순히 어느 방향으로 몇 번 갔는지 곱하기만 하면 됩니다. 시간 복잡도는 그냥 깡 브루트 포스를 하면 O(nmQ)였습니다. nm이 1만이고, Q가 200만이면, 시간초과 나기 딱 좋습니다. 이것을 O(32Q)로 줄일 수 있습니다.