문제 이해 단계
https://www.acmicpc.net/problem/16926
문제 조건만 보면 무슨 소리인지 전혀 모르겠는데
밑에 첨삭된 그림을 보면 어떤 식으로 배열하라는지 바로 알겠다.
그림처럼 가운데를 중심으로 X자 모양으로 2개의 직선과
+ 모양으로 2개의 직선을 그리는 것이다.
그리고 가운데를 중심으로 45도를 단위로 돌렸을 때의 결과를 구하는 문제이다.
문제 접근 단계
해당 문제에서 요구하는 것은 배열을 회전시키는 것이다.
회전시켰다는 것을 확인하기 위해
12시 방향에 있던 5가 3시 방향에 위치하는 등, 어떤 그룹의 이동을 통해 확인한다.
여기서 생각이 든 게, 저 배열들을 확실한 그룹으로 나눌 수 없을까?
아래 그림같이 나누면 n이 아무리 늘어나도
같은 방식으로 포함시키면 되기 때문에 같은 특성을 가질 것이다.
직선은 쭉 확장되기 때문이다.
이렇게 선을 긋고 그룹을 만들어보니, 이게 약간 시계처럼 보이기 시작했다.
그래서 이를 한번 시계처럼 생각해 봤다.
초록 선의 11 부분을 9시
빨간 선의 숫자 1 부분을 10시 30분 정도 (편의상 10시)
검은 선의 숫자 3 부분을 12시
파란 선의 숫자 5 부분을 1시 30분 정도 (편의상 2시)
이제 각 시점을 배열로 생각해 보자.
그러면 이렇게도 볼 수 있다.
현재 9시 배열의 원소는 {11,12,13,14,15}(즉, 초록선)이고,
10시 배열의 원소는 {1,7,13,19,25}(즉, 빨간색)이고,
...
이렇게 생각한다면,
45도에 해당하는 시점(배열)은 움직이지 않고,
그 안에 있는 원소 뭉치들이 회전한다고 볼 수 있다.
이 말이 무슨 말이냐면, 만약 위의 그림이 시계방향으로 45도 돌아가면
빨간 선이 12시 방향으로 올 것이다.
그렇다면 이렇게도 볼 수 있는 것이다.
12시 배열의 원소가 {3,8,13,18,23}에서
{1,7,13,19,25}로 바뀌었다.
여기서 한 가지 중요한 점은
그 원소 뭉치들의 순서와 내용은 절대 바뀌지 않는다는 것이다.
초록선, 빨간 선, 검은선, 파란 선은 아무리 회전을 해도
그 구성요소들과 순서가 바뀌지 않는다.
그리고 배열 간의 순서 또한 존재하는데, 그 순서 또한 변하지 않는다.
무조건, 9시 다음에는 10시,
그다음에는 12시, 그다음에는 2시가 와야 한다.
이 순서라는 점을 덱을 활용하여 답을 구할 수 있다.
상관없는 다른 배열들은 빼고 그리겠다.
각각의 선들을 배열로 표시했다.
13은 공통으로 사용되기 때문에 노란색으로 표시했다.
해당 시간 순서는 무조건 동일하게 유지돼야 한다.
그래서 9시부터 시계방향으로 덱에 9시에 있는 원소(배열 요소)부터 넣는다.
그럼 큐에 9시 -> 10시 -> 12시 -> 2시 순으로 담기게 된다.
이제부터 큐에 각 자리는 시각을 의미하게 된다.
덱이 push나 pop을 통해 9시 자리에 파란색 요소가 오게 되면,
9시 배열의 원소는 파란색 요소가 되는 것이다.
먼저, 반시계 방향으로 돌 때부터 알아보면 이렇게 된다.
1. d/45(45씩 몇 번?) 횟수를 하나씩 front 쪽으로 빼준다.
2. 빼준 블록의 배열 순서를 역순으로 재배열한다.
3. 덱에 back 쪽으로 다시 넣는다.
왜 이런 식이 되는지 그림을 통해 알아보자.
먼저 d가 45일 때, front에 가장 위에 블록 하나를 back 쪽으로 옮기는 그림과
배열 그림에서 반시계 방향으로 45도 돌아갔을 때 어떻게 되는지 보자.
9시 자리에 있던 초록색이 순서는 역순으로 바뀌었지만,
2시 자리로 바뀐 것을 확인할 수 있다.
더불어 다른 배열들도 정상적으로 바뀐 것을 확인할 수 있다.
하지만, 사실 초록색은 2시 자리임과 동시에 7시 30분(왼쪽 대각선 아래)을 의미하기도 한다.
사실 그래서 배열 요소의 방향에 따라 2시 인지, 7시 30분 인지도 구분해줘야 한다.
나는 순서를 쓰기 싫어서, 그냥 덱에 자리를 4개 더 늘려서 똑같은 작업을 하려고 했는데,
그럴 필요가 없었다.
왜냐하면 서로 마주 보고 있는 시점들의 원소들은 모두 같기 때문이다.
다른 것은 원소 배열 순서가 정확히 서로의 역순이라는 점이다.
즉, 9시 자리가 7시 30분 자리로 옮겨진 후
이 값을 역순으로 배열하면 2시가 된다는 뜻이다.
그래서 빼줌과 동시에 그 블록의 배열을 역순으로 만든다.
90도를 돌리던 135도를 돌리던 45도씩 돌아가므로
다른 요소들 전부 45도씩 돌아가는 법칙을 따른다.
이제 시계방향으로 돌릴 때는 보면 사실 똑같다.
그냥 빼는 방향이 다를 뿐이다.
시계 방향으로 돌릴 때는 back 쪽에서 빼주고, 역순 재배열 후 front 쪽으로 넣는다.
이렇게 하는 이유와 법칙은 반시계와 완벽히 동일하다.
이제 이를 코드로 구현하면 된다.
문제 구현 단계
int map[501][501]; // 전체 맵의 크기
vector<int> direct[4]; // 9시 10시 12시 2시 순서
deque<vector<int>> order; // 덱
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) {
cin >> map[i][j];
if(i == n/2) direct[0].push_back(map[i][j]);
if(j == i) direct[1].push_back(map[i][j]);
if(j == n/2) direct[2].push_back(map[i][j]);
if(j == (n-1)-i) direct[3].push_back(map[i][j]);
}
}
// 구한 방향 정보 벡터들을 덱에 순서대로 넣음
for(auto iter : direct) order.push_back(iter);가장 먼저 입력을 받는 부분이다.
여기서 direct [4]를 사용했는데, 0~4까지 각각 9,10,12,2시 순서이다.
이는 각 자리가 그 시각을 의미하기 때문에 값을 넣을 때 순서를 다르게 해서는 안된다.
맵 정보를 입력받을 때, 시각 순서에 맞게 올바르게 값을 넣은 후 이를 덱에 넣는다.
int count = (d >= 0)? d / 45 : d/45 * -1; // 반복 횟수
while(count--){
vector<int> tmp;
// 반시계 방향
if(d < 0){
// 가장 앞에서 꺼낸 블록 저장
tmp = order.front();
reverse(tmp.begin(),tmp.end()); // 역순
order.pop_front();
order.push_back(tmp); // 맨 뒤에 다시 넣음
}
// 시계 방향
else if(d > 0){
// 가장 뒤에 있는 블록
tmp = order.back();
reverse(tmp.begin(),tmp.end());
order.pop_back();
order.push_front(tmp); // 맨 앞에 넣음
}
}위에서 말한 d/45 횟수만큼 push와 pop을 반복해 주는 코드이다.
여기서 덱을 쓴 이유가 나온다.
반시계와 시계방향이 있어서
앞과 뒤에서 둘 다 빼고 넣을 수 있어야 하기 때문이다.
중간에 reverse 함수를 통해 벡터 안에 있던 값을 뒤집는다.
int k = 0; // 시간 인덱스
while(!order.empty()){
// direct 배열 정보를 덱에 있는 정보로 갱신
direct[k] = order.front();
order.pop_front();
k++;
}
int x,y;
x = y = n/2;
for(int i = 0; i < 4; i++){
for(int j = 0; j < direct[i].size(); j++){
if(i == 0) map[x][j] = direct[i][j];
else if(i == 1) map[j][j] = direct[i][j];
else if(i == 2) map[j][y] = direct[i][j];
else if(i == 3) map[j][n-1-j] = direct[i][j];
}
}마지막으로 덱에 있는 값을 다시 순서대로 빼내어
direct배열에 순서대로 넣어준다.
그 값을 초기에 주어졌던 맵에 넣어주면 완성이다.
아래는 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <vector>
#include <deque>
#include <cstring>
#include <algorithm>
using namespace std;
int map[501][501];
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T;
cin >> T;
while(T--){
int n,d;
cin >> n >> d;
//9 10 12 2 순서
vector<int> direct[4];
deque<vector<int>> order;
memset(map,0,sizeof(map));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) {
cin >> map[i][j];
if(i == n/2) direct[0].push_back(map[i][j]);
if(j == i) direct[1].push_back(map[i][j]);
if(j == n/2) direct[2].push_back(map[i][j]);
if(j == (n-1)-i) direct[3].push_back(map[i][j]);
}
}
for(auto iter : direct) order.push_back(iter);
int count = (d >= 0)? d / 45 : d/45 * -1;
while(count--){
vector<int> tmp;
if(d < 0){
tmp = order.front();
reverse(tmp.begin(),tmp.end());
order.pop_front();
order.push_back(tmp);
}
else if(d > 0){
tmp = order.back();
reverse(tmp.begin(),tmp.end());
order.pop_back();
order.push_front(tmp);
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) cout << map[i][j] << " ";
cout << "\n";
}
}
}
시행착오
해당 문제는 내가 구현이 부족하다는 문제점이 있어서
구현 문제를 많이 풀어보는 도중에 푼 문제인데, 회전에 관한 문제라 생각이 오래 걸렸다.
푸는 데는 딱히 어렵지는 않았는데,
그냥 내가 푼 풀이가 좀 괜찮은 거 같아서 그냥 공유해보고 싶었다.