문제 이해 단계
문제 자체를 NxM 배열이 주어지고 회전 횟수 R이 주어진다.
회전 횟수 R만큼 반시계방향으로 예제로 주어진 패턴처럼 돌리면 된다.
그림을 보면 쉽게 패턴 파악이 가능하기 때문에 따로 설명은 안 하겠다.
문제 접근 단계
이 문제는 배열을 반시계방향으로 회전시키는 것이기 때문에, 단순 구현 문제에 해당하는 것 같다.
문제는 같은 행이나 열에 있는 것은 그냥 오른쪽에 있는 값을 가져오면 되는데,
각 모서리에 있는 값 같은 경우는 가져와야 하는 부분이 각각 다르다.
예를 들어 아래 그림과 같이 왼쪽 위는 오른쪽에서,
오른쪽 위는 아래에서,오른쪽 아래는 왼쪽에서,
왼쪽 아래는 위에서 가져와야 한다.
이 규칙은 안에 있는 사각형에도 모두 적용된다.
그래서 왼쪽 위를 기준으로
대각선으로 줄어들면서 반복하기로 했다.
사각형 테두리를 순회하는 방법은
현재 위치를 나타내는 포인터를 둠으로써 구현하였다.
왼쪽 위에서 출발해서 오른쪽 끝에 다다르면 아래로 이동,
그다음 왼쪽, 그다음은 위로 이동하는데,
구현 문제이니만큼 문제 구현 단계에서 코드로 설명한다.
다음으로 고려해봐야 할 것은 M*N 맵이고,
1번 회전할 때 총 사각형 테두리를 도는 행위를 몇 번 해야 하는가이다.
여기서는 문제 제한 조건에서 큰 힌트가 있는데
min(N, M) mod 2 = 0
즉, 행과 열 중 작은 것은 무조건 짝수라는 뜻이다.
그래서 아래 그림에 다양한 예시를 보면 알 수 있겠지만,
반복 횟수가 정확히 행과 열 중 작은 것의 절반인 것을 확인할 수 있다.
즉 반복 횟수 = min(N, M) / 2이다.
이제 위의 정보들을 이용하여 코드로 구현해 보자
문제 구현 단계
vector<vector<int>> solution(vector<vector<int>> origin,int n, int m){
vector<vector<int>> temp = origin;
// 반복 횟수
int repeat = min(n,m) / 2;
// 해당 위치 방문 확인
bool visited[300][300] = {false,};
for(int size = 0; size < repeat; size++){
// size -> 사각형 테두리 시작점
int cntX = size, cntY = size;
// 다시 한번 시작위치를 방문할 때 까지 반복
while(!visited[cntX][cntY]){
visited[cntX][cntY] = true;
// 위 일때
if(cntX == size && cntY != m-1-size){
// temp 현재 위치에 origin의 다음 위치 값을 담아줌
temp[cntX][cntY] = origin[cntX][cntY+1];
cntY++;
}
// 오른쪽 일 때
else if(cntY == m-1-size && cntX != n-1-size){
temp[cntX][cntY] = origin[cntX+1][cntY];
cntX++;
}
// 아래 일 때
else if(cntX == n-1-size && cntY != size){
temp[cntX][cntY] = origin[cntX][cntY-1];
cntY--;
}
// 왼쪽 일 때
else if(cntY == size && cntX != size){
temp[cntX][cntY] = origin[cntX-1][cntY];
cntX--;
}
}
}
return temp;
}배열을 회전시키는 solution 함수이다.
매개변수로 현재 맵의 상태, 가로길이, 세로 길이를 받는다.
이차원 배열을 위해 이중벡터를 사용하였다.
반복 횟수는 아까 말했다시피 n과 m 중 작은 값의 / 2이고,
cntX와 cntY로 현재 x위치와 y위치를 확인한다.
그리고 모든 사각형 테두리를 다 돌았는지 확인해 주기 위해
visited이라는 방문 확인용 bool을 만들어주었다.
여기서 size는 cntX와 cntY의 시작점의 오프셋을 말하는 것인데,
처음에는 (0,0)이지만 그다음 사각형 테두리는 (1,1), (2,2)..
이런 식이기 때문에 size를 1씩 올려줘야 한다.
나머지 조건문은 각 위치에 따른 행동을 다르게 해 줬다.
반시계로 돌리는 방법은 임의의 2차원 배열 temp를 만들고,
현재 위치에 원래 배열의 다음 값을 담음으로써, 마치 회전하는 것처럼 값을 담는 것이다.
코드는 그렇게 복잡하진 않은데 막상 구현하려니까 어렵더라.
마지막으로 전체 코드를 올리고 코드를 끝내겠다.
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> solution(vector<vector<int>> origin,int n, int m){
vector<vector<int>> temp = origin;
// 반복 횟수
int repeat = min(n,m) / 2;
// 해당 위치 방문 확인
bool visited[300][300] = {false,};
for(int size = 0; size < repeat; size++){
// size -> 사각형 테두리 시작점
int cntX = size, cntY = size;
// 다시 한번 시작위치를 방문할 때 까지 반복
while(!visited[cntX][cntY]){
visited[cntX][cntY] = true;
// 위 일때
if(cntX == size && cntY != m-1-size){
// temp 현재 위치에 origin의 다음 위치 값을 담아줌
temp[cntX][cntY] = origin[cntX][cntY+1];
cntY++;
}
// 오른쪽 일 때
else if(cntY == m-1-size && cntX != n-1-size){
temp[cntX][cntY] = origin[cntX+1][cntY];
cntX++;
}
// 아래 일 때
else if(cntX == n-1-size && cntY != size){
temp[cntX][cntY] = origin[cntX][cntY-1];
cntY--;
}
// 왼쪽 일 때
else if(cntY == size && cntX != size){
temp[cntX][cntY] = origin[cntX-1][cntY];
cntX--;
}
}
}
return temp;
}
int main(){
int N,M,R;
vector<vector<int>> map;
cin >> N >> M >> R;
for(int i = 0; i < N; i++){
vector<int> tmp;
for(int j = 0; j < M; j++){
int val;
cin >> val;
tmp.push_back(val);
}
map.push_back(tmp);
}
vector<vector<int>> answer;
while(R--) map = solution(map,N,M);
answer = map;
for(int i = 0; i < answer.size(); i++){
for(int j = 0; j < answer[i].size(); j++)
cout << answer[i][j] << " ";
cout << '\n';
}
}
시행착오
아이디어는 쉽게 떠올라서 그냥 구현 기초 문제인 줄 알았는데
구현이 생각보다 오래 걸렸다.
아니 한참 걸렸다. 왜 이걸 못 풀지?
자괴감도 많이 들고 내가 아직 기초도 부족하다는 생각이 들 만큼 한심해 보였다.
segmentFault도 많이 뜨고 빨리 다음 구현 문제나 풀어봐야겠다.