[C++] 백준/BOJ - 16927 : 배열 돌리기 2

---

문제 이해 단계

 

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

배열 돌리기 시리즈 문제

NxM 직사각형을 R번 회전시킨다.

회전시킬 때 한 칸씩 반시계 방향으로 돌아가는데, 직사각형 안에 직사각형이 있는 구조다.
그림을 보면 이해가 빠를 것이다.

이런 상황일 때 R번 회전시켰을 때의 결과를 구하는 것

 

 

---

문제 접근 단계

이전에 풀었던 배열 돌리기와 방향만 다르지 완전히 똑같은 문제 아닌가?
라고 생각했는데 제한 조건을 보니 아니었다.

R이 최대 10^9이라는 점..

이전 문제는 한 칸씩 이동시키는 것으로 구현했었다.
이 문제는 그렇게 하면  최악의 경우 10^9 번 이동시켜야 한다. 
그럼 당연히 시간초과가 뜨겠지..

해당 문제에서 구현해야 할 것은
어떻게든 R을 줄여서 이동하는 로직을 구현하는 것이다.

 

---

이동 횟수 R 최소화하기

한 번에 R칸 이동하는 로직을 구현하는 것이라고 해도
최대 10^9 칸 이동하게 하는 것은 너무 비효율적이다.

그래서 이 이동은 회전이기 때문에 움직이다 보면 결국 첫 상태에 도달하게 된다.
이를 이용해서 이동 횟수 R을 최소화하겠다.

 

 

이렇게 4x6 짜리 직사각형이 있다고 가정해 보자.

가장 바깥 직사각형이 처음 상태로 돌아오기 위해서는 몇 칸을 움직여야 할까?

32칸 움직이면 제자리로 돌아온다.
즉, 0 ~ 31칸 사이에서만 다른 형태가 나오므로 R%32를 통해 R을 최소화할 수 있다.  

N과 M으로 이를 구하는 여러 방법이 있겠지만
나는 N*2+(M-2)*2를 사용하였다. 

그럼 전체 직사각형에 대해서 R%32를 하면 될까? 그렇지 않다.
내부에 사각형은 또 따로 움직이기 때문이다.

안쪽 직사각형만 보자. N과 M이 2씩 작아졌다. 
그럼 해당 직사각형은 8칸이면 다시 제자리로 돌아오게 된다.

즉, 안쪽 직사각형에 대해서는 R%8을 적용해야 한다는 것이다. 

직사각형이 처음의 상태로 돌아오는 수를 주기라고 한다면,
주기는 직사각형마다 다르게 계산해줘야 한다.

여기서 직사각형이 한 단계 작아질 때
가로, 세로가 2씩 작아지기 때문에 계산식에 N-2, M-2를 적용하여 계산해 준다.

그리고 R% 주기를 통해 나오는 값을 통해 R을 최소화할 수 있다.
이를 통해 10^9 이 최대 300*2 + 300*2 - 4 = 1196으로 바뀌었다.(N과 M이 최대 300)

 

---

회전시키기

R을 최소화했으니 이제 R칸을 이동시켜 보자.
내가 사용한 방법은 약간 BFS와 닮아있다.

문제에서는 반시계방향으로 돌리는 것인데,
사실상 시계 방향에 있는 값을 반시계 방향으로 가져오는 것이다.

따라서 해당 자리의 값을 찾을 때는 시계방향에서 찾아야 하므로
방향을 탐색해 줄 때는 시계방향으로 탐색해 준다.

 

시작 위치부터 시계방향(필자는 오른쪽 방향부터)
한 칸씩 한 방향으로 전진시키며 값을 넣는다.

그러다가 M의 범위를 벗어나는 순간 방향을 다음 시계 방향으로 바꾼다(필자는 아래)

 

이런 식으로 모든 방향에 대해 반복하다, 다시 처음 위치로 돌아오면 끝낸다.
여기까지가 회전을 한번 진행한 것이다.

이 회전을 직사각형마다 R을 최소화한 횟수만큼 진행하면 된다.

 

이를 코드로 구현해 내면 된다.

 

---

문제 구현 단계

int N,M,R;
int map[301][301];

// 위,왼,아래,오른
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

// 회전(시작 위치, 직사각형 주기)
void rotate(int start, int size){
    int repeat = R%size; // R을 최소화한 반복값

    while(repeat--){
        int val = map[start][start]; // 첫 위치값
        int x = start;
        int y = start;
        int k = 0;

        // 모든 방향에 대해 반복
        while(k < 4){
            int nx = x + dx[k];
            int ny = y + dy[k];
            // 첫 위치로 돌아오면 while문 종료
            if(nx == start && ny == start) break;
            // 직사각형 M과 N 범위안에 있을때만
            if((start <= nx && nx < N- start) && (start <= ny && ny < M-start)){
                map[x][y] = map[nx][ny]; // (x,y) : 값을 받을 위치 , (nx,ny) : 값을 줄 위치
                // 해당 위치로 x와 y를 변경
                x = nx; 
                y = ny;
            }
            // 없다면 범위를 벗어난것이기 때문에 다음 방향 탐색
            else k++;
        }
        map[start+1][start] = val; // 마지막 값은 비어있을테니 빼뒀던 값을 넣어둠
    }
}

회전을 하는 rotate함수이다.
인자로 탐색을 시작하는 위치 start와 직사각형의 주기 size를 받는다.
주기 size는 N*2+(M-2)*2를 계산한 결과이다.

R% size를 이용하여 반복 횟수를 구하고 반복을 시작한다.
이때부터 BFS와 유사하게 진행된다.

시계방향 순서대로 한 방향으로 N과 M의 범위를 벗어날 때까지
시계 방향에 있는 값을 반시계 방향에 있는 위치에 넣는 것을 반복한다. 벗어나면 바로 위치를 바꾼다.

이걸 쭉 반복하다가 처음 위치로 돌아오면 종료하고,
반복의 마지막 위치는 값을 주기만 하고 받지는 못했다.

원래대로라면 start위치에 있던 값을 가져와야 하므로, 임의로 값을 지정해 준다.

이걸 반복 횟수만큼 반복해 주는데, 직사각형 따로따로 해주는 것이다.

int sizeN = N;
int sizeM = M;

int mapSize = min(N,M)/2; // 전체 반복 횟수

for(int i = 0; i < mapSize; i++){
    	// 인덱스 i = 0 부터 시작
        rotate(i,sizeN*2+(sizeM-2)*2);
        
        // 2씩 줄어들기 때문
        sizeN -= 2;
        sizeM -= 2;
}

main문에 있던 코드를 일부 가져왔다.
rotate를 호출하기 위한 반복문이다.

mapSize는 전체적인 반복문,
즉 직사각형의 개수를 몇 개인지 계산하여 반복 횟수를 구한다.

그리고 N과 M의 값을 통해 연산을 하고 2씩 줄여주는 과정을 반복한다.

이게 모든 코드의 설명의 끝이다.
이제 아래에 전체 코드를 올리고 끝내겠다.

#include <iostream>

using namespace std;


int N,M,R;
int map[301][301];

// 위,왼,아래,오른
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

// 회전(시작 위치, 직사각형 주기)
void rotate(int start, int size){
    int repeat = R%size; // R을 최소화한 반복값

    while(repeat--){
        int val = map[start][start]; // 첫 위치값
        int x = start;
        int y = start;
        int k = 0;

        // 모든 방향에 대해 반복
        while(k < 4){
            int nx = x + dx[k];
            int ny = y + dy[k];
            // 첫 위치로 돌아오면 while문 종료
            if(nx == start && ny == start) break;
            // 직사각형 M과 N 범위안에 있을때만
            if((start <= nx && nx < N- start) && (start <= ny && ny < M-start)){
                map[x][y] = map[nx][ny]; // (x,y) : 값을 받을 위치 , (nx,ny) : 값을 줄 위치
                // 해당 위치로 x와 y를 변경
                x = nx; 
                y = ny;
            }
            // 없다면 범위를 벗어난것이기 때문에 다음 방향 탐색
            else k++;
        }
        map[start+1][start] = val; // 마지막 값은 비어있을테니 빼뒀던 값을 넣어둠
    }
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> N >> M >> R;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++) cin >> map[i][j];
    int sizeN = N;
    int sizeM = M;

    int mapSize = min(N,M)/2; // 전체 반복 횟수

    for(int i = 0; i < mapSize; i++){
        // 인덱스 i = 0 부터 시작
        rotate(i,sizeN*2+(sizeM-2)*2);

        // 2씩 줄어들기 때문
        sizeN -= 2;
        sizeM -= 2;
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++) cout << map[i][j] << " ";
        cout << "\n";
    }
}

 

 

---

시행착오

머리 터질뻔해서 겨우겨우 구현했더니만 시간초과,
방법 바꿔서 구현했더니 시간초과, 그냥 시간초과, 틀렸습니다.

이틀을 이 문제에 쏟았는데도 안 풀려서 결국에는 인터넷의 힘을 빌렸다.
다른 분들의 풀이를 보고도 이해하는데 좀 걸렸다.

BFS방식을 사용해서 이 문제를 풀 수도 있구나..
난 계속해서 배열을 직접 건드리면서 머리 아프게 했는데..
역시 사람은 똑똑해야 해. 인터넷 잘 참고해야지

아래는 내가 이해하는데 도움이 많이 됐던 블로그이다!!

 

https://nanyoungkim.tistory.com/79

[C++] 백준 16927번 - 배열 돌리기2 (시뮬레이션/구현)