BOJ - 배열 돌리기 2 (16927)

https://www.acmicpc.net/problem/16927

16927번: 배열 돌리기 2

 

그냥 구현 문제입니다.

주어지는 R 값이 매우 큰데 이대로 한 칸씩 돌리면서 돌면 당연히 시간초과가 나겠죠.

배열의 고리의 길이로 나눈 나머지만 돌면 됩니다.

 

자칫하면 코드가 길어질 수도 있는 문제입니다.

두 가지 방법으로 풀어봤습니다.

 

1. 

처음 아이디어는 '좌표를 한 번에 알면 쉽게 풀 수 있겠다' 라는 생각에서 시작했습니다.

즉, 원래 배열에서 좌표가 회전 후에 어디 좌표로 들어가는지 알면 쉽게 해결할 수 있습니다.

2차원 배열에서 직접 이동하는 것을 처리해주는게 귀찮으므로(방향과 경계값 처리), 1차원 배열로 저장해 놓으면

이동하는 것을 처리해주기가 훨씬 수월합니다.

 

바깥쪽 고리부터 시작해, 안쪽 고리로 진행해 가면서 각 고리의 좌표들을 벡터에 담습니다.

vector<pii> v[301] 이라고 정의가 되어 있는데요. 인덱스는 각 고리의 번호를 뜻 합니다.

각 고리의 좌표를 담을 때, (i, i) 부터 시작해서 반시계 방향으로 진행해가며 담습니다.

그 이유는 문제에서 반시계 방향 회전을 요구하기 때문입니다. 우선 이에 맞춰서 

dy, dx 배열도 적절히 조절을 해줘야겠죠.

 

고리별로 좌표를 다 모았으면, 이제 회전을 해봅시다. 

R 값이 매우 크므로 고리의 크기로 나눈 나머지만 돌립니다. 원 모양이므로 주기가 반복되기 때문이죠.

 

#include <iostream>
#include <iterator>
#include <vector>
#define endl    '\n'
using namespace std;
 
typedef pair<int, int> pii;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
 
int n, m, k;
int mp[301][301];
int mp2[301][301];
bool chk[301][301];
vector<pii> v[301];
 
bool range(int y, int x) {
    return !(y < 0 || y >= n || x < 0 || x >= m);
}
 
int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) 
            cin >> mp[i][j];
                
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int y = i, x = i;
        if (chk[y][x]) break;
        cnt += 1;
        v[i].push_back({ y,x });
        chk[y][x] = true;
        for (int dir = 0; dir < 4; dir++) {
            while (1) {
                int ny = y + dy[dir], nx = x + dx[dir];
                if (!range(ny, nx) || chk[ny][nx]) break;
                y = ny, x = nx;
                v[i].push_back({ ny,nx });
                chk[ny][nx] = true;
            }
        }
    }
 
    for (int i = 0; i < cnt; i++) {
        int move = k % v[i].size();
        for (int j = 0; j < v[i].size(); j++) {
            int ch_pos = (j + move) % v[i].size();
            int ch_y = v[i][ch_pos].first, ch_x = v[i][ch_pos].second;
            int fr_y = v[i][j].first, fr_x = v[i][j].second;
            mp2[ch_y][ch_x] = mp[fr_y][fr_x];
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << mp2[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

 

 

2.

두번째 아이디어는 직접 이동해가면서 써주는 방식입니다.

위에서 언급했듯이, 방향과 경계값을 처리해주는게 귀찮습니다.

중복되는 부분을 go라는 함수로 빼줬는데, 이 디자인을 처음하면 빠르게 떠올리기가 쉽지

않을 것 같아요. go 함수는 방향과 경계값을 모두 처리해주고 어디로 이동했는지까지 처리해 주는

함수입니다.

 

 

#include <iostream>
#define endl    '\n'
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int arr[301][301];
int ans[301][301];
int n, m, r;
 
bool range(int y, int x, int lb_n, int ub_n, int lb_m, int ub_m) {
    return !(y < lb_n || y > ub_n || x < lb_m || x > ub_m);
}
 
void go(int &sy, int &sx, int &dir, int lb_n, int ub_n, int lb_m, int ub_m) {
    while (1) {
        int ny = sy + dy[dir], nx = sx + dx[dir];
        if (!range(ny, nx, lb_n, ub_n, lb_m, ub_m)) {
            dir = (dir + 1) % 4;
            continue;
        }
        sy = ny, sx = nx;
        return;
    }
}
 
int main() {
    FastIO;
    cin >> n >> m >> r;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];
 
    for (int i = 0;; i++) {
        int cy = i, cx = i, c_dir = 0;
        if (ans[cy][cx]) break;
        int step = r % (2 * (m + n - 4 * i) - 4);
        while (step--) go(cy, cx, c_dir, i, n - i - 1, i, m - i - 1);
        step = 2 * (m + n - 4 * i) - 4;
        int oy = i, ox = i, o_dir = 0;
        while (step--) {
            ans[cy][cx] = arr[oy][ox];
            go(oy, ox, o_dir, i, n - i - 1, i, m - i - 1);
            go(cy, cx, c_dir, i, n - i - 1, i, m - i - 1);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << ans[i][j] << ' ';
        cout << endl;
    }
 
    return 0;
}