문제 하나 더!
지난 네이버 코테때 출제되었던 문제와 유사한 느낌을 받았던 BOJ 16926 배열 돌리기 를 풀어보았다. 보면 기본적인 구현 문제 처럼 보이지만 막상 풀려니 난 이런 유형에 꽤나 약하다고 느꼈다.
네이버 기출도 난이도가 그리 높지 않아 보였는데 경험이 부족해서 풀지 못했던 것 같다,,! 역시 알골은 많이 다양하게 풀어보는게 짱인 것 같다.
BOJ 16926 배열 돌리기
크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.
A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
↓ ↑
A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5]
↓ ↓ ↑ ↑
A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5]
↓ ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.
1 2 3 4 2 3 4 8 3 4 8 6
5 6 7 8 1 7 7 6 2 7 8 2
9 8 7 6 → 5 6 8 2 → 1 7 6 3
5 4 3 2 9 5 4 3 5 9 5 4
<시작> <회전1> <회전2>
배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.
입출력
[입력]
첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.
둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.
[출력]
입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.
[제한]
- 2 ≤ N, M ≤ 300
- 1 ≤ R ≤ 1,000
- min(N, M) mod 2 = 0
- 1 ≤ Aij ≤ 108
나의 풀이
일단 문제는 재귀적으로 반복되는 형식이다.
동일한 방식이 가장 바깥쪽에서부터 안쪽까지 적용되기 때문에 하나의 사이클에 대해서만 풀어낸다면 같은 방법으로 풀 수 있다.
이 문제는 비교적 간단한 편이었던 것이 문제 조건 중 min(N, M) mod 2 = 0 이 있었기 때문이다. 여러가지 형태로 구성될 수 있는 2차원 배열이지만 이 조건을 통해 입력되는 배열은 남는 요소 없이 배열의 모든 요소가 어떠한 사이클에 포함된다는 것을 알 수 있었다.
배열에서 원소가 교체되는 원, 사이클은 총 min(N, M) / 2 개 만큼 생성되기 때문에 우리는 min(N, M) / 2 번만 원소들을 원을 따라 교체해 주면 된다.
원소를 교체하는 방법에서 뜻밖에 조금 애를 먹었는데 차근차근 그림으로 그려 시뮬레이션 하여 어렵지 않게 해결할 수 있었다.
네가지 진행 방향 (아래로, 우로, 위로, 좌로)에 따른 인덱스 변화를 지정해두고 진행 방향에 따라 구한 다음 좌표가 현재 사이클 범위를 벗어난다면 진행 방향 변수를 증가시켜 꺾이는 지점을 다루어 주었다.
모든 진행 방향대로 원소 교체가 끝난 뒤에는 사이클을 종료 시켰고, min(N, M) / 2 개 만큼의 사이클 대로 원소를 교체하는 과정을 R번 반복한 뒤 배열을 출력하였다.
코드
#include <iostream>
#include <vector>
// boj 16926 배열 돌리기, 복잡 구현, 실버 2
using namespace std;
vector<vector<int>> map;
// 이동 방향 0 : 아래로, 1 : 오른쪽으로, 2 : 위로, 3 : 왼쪽으로
// 이동 방향별 다음 index 값 변화
int dy[4] = {+1,0,-1,0};
int dx[4] = {0,1,0,-1};
void rotateMap(int N, int M, int R){
int count = R;
int cycle = min(N, M)/2;
while (count>0){ // R 번 진행
count--;
vector<vector<bool>> visited(N, vector<bool>(M, false));
for (int i = 0; i < cycle; ++i) { // 배열 내에 생기는 사이클 만큼 교환 진행
int dir = 0;
pair<int, int> cur = {i, i};
pair<int, int> next = {cur.first+dy[dir], cur.second+dx[dir]};
int before = map[cur.first][cur.second];
int after = map[next.first][next.second];
while (!visited[next.first][next.second]){
map[next.first][next.second] = before;// 값 교체 후
visited[next.first][next.second] = true;
before = after;
cur = next; //다음 위치로 이동
next = {cur.first+dy[dir], cur.second+dx[dir]};
// 다음 위치가 범위 벗어나면 이동 방향 변화
if (next.first<i || next.first>=N-i || next.second<i || next.second>=M-i){
if(dir<3){
dir++;
next = {cur.first+dy[dir], cur.second+dx[dir]};
}else{
break;
}
}
after = map[next.first][next.second];
}
}
}
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, R;
cin>>N>>M>>R;
map.assign(N, vector<int>(M));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin>>map[i][j];
}
}
rotateMap(N,M,R);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cout<<map[i][j]<<' ';
}
cout<<'\n';
}
return 0;
}