[C++] 백준/BOJ - 17406 : 배열돌리기 4

---

문제 이해 단계

배열 돌리기 시리즈 문제.

NxM 크기인 배열에 K개의 회전 연산 (r, c, s)이 들어오는데,
이건 NxM안에 포함된 정사각형을 의미한다.

이 정사각형의 크기는 왼쪽 위 대각선은
(r-s, c-s)을 오른쪽 아래 대각선은 (r+s, c+s)를 가진다.

이 정사각형은 위에 그림처럼 회전하게 된다.
K개의 회전이 끝난 후 각 행의 합 중 가장 작은 값을 답으로 출력한다.

K개의 회전연산의 순서는 임의로 섞을 수 있으며, 최소 값이 나오도록 해야 한다.

 

 

---

문제 접근 단계

배열 돌리기 시리즈 문제인데, 돌아가는 패턴 자체는 익히 봐왔던 패턴이다.
이 패턴을 시계방향을 돌린다.

다른 점은 총 2가지인데 회전하는 정사각형이 따로 있다는 점과,
회전 순서를 섞을 수 있다는 것이다.

NxM 배열에서 회전 연산 (r, c, s)이 주어져서
NxM에 포함된 새로운 정사각형에서 회전일 실행해야 한다.

또한 회전 연산은 여러 번 가능한데, 순서를 임의로 섞을 수 있다.
따라서 순서에 따라 결과가 달라지기 때문에 나올 수 있는 최솟값 또한 달라진다.

그렇기 때문에 우리는 모든 회전 연산 순서에 대해 회전을 돌려줘야 한다.
이를 구해주는 방법으로 백트래킹을 선택하였다.

백트래킹을 통해 모든 회전 연산 순서에 대한 결과에 대한 최솟값을 구하고, 그중 가장 작은 값을 구한다.

이러한 구현적인 부분은 문제 구현 단계에서 구체적으로 다루겠다.

 

 

---

문제 구현 단계

int findMin(){
    int minVal = INT32_MAX;
    for(int i = 1; i <= N; i++){
        int val = 0;
        for(int j = 1; j <= M; j++){
            val += map[i][j];
        }
        minVal = min(minVal,val);
    }
    return minVal;
}

// 회전 연산의 순서에 대한 모든 경우에 대해 시행
void backTracking(int idx){
    // 회전 연산의 개수를 초과했을 때
    if(idx >= K){
        // 최초의 맵(origin)을 map으로 복사(초기화)
        for(int i = 1; i <= 50; i++)
            for(int j = 1; j <= 50; j++) map[i][j] = origin[i][j];

        // 저장된 회전연산 순서대로 회전 실행
        for(int i = 0; i < order.size(); i++) {
            int tmp = order[i];
            rotate(tmp); // 회전
        }
        
        ans = min(ans,findMin()); // 최솟값 계산
        return;
    }

    // 백트래킹
    for(int i = 0; i < K; i++){
        if(v[i]) continue; // 이미 방문한 곳은 제외
        v[i] = true; // 방문 처리
        order.push_back(i); // 순서대로 담음
        backTracking(idx+1); // 다음 함수 호출
        order.pop_back(); // 호출 종료시 담아뒀던 그 인덱스 제거
        v[i] = false; // 방문 처리 해제
    }
}

K개의 회전 연산의 순열, 즉 모든 순서 경우의 수에 대해 실행하는 백트래킹이다.
idx는 현재까지 실행한 회전연산의 개수를 의미한다.

idx는 0부터 시작하기 때문에 K개가 됐다는 것은
회전 연산의 개수를 다 썼다는 뜻이므로 맵을 회전시키기 시작한다.

먼저 origin에 있던 원래 맵의 정보를 map에 복사하여 초기의 맵으로 초기화한다.
그 후 order에 담겨있는 순서대로 회전을 실행한다.

회전을 종료되면 findMind을 통해 최솟값을 구하게 된다.

그 아래에 있는 것이 백트래킹을 통해 order에 회전 연산의 순서를
재귀호출을 통해 나올 수 있는 모든 경우의 수를 담는다.

이는 순열을 구현하는 일반적인 형태이기 때문에 알아두는 것이 좋다. 

order에 해당 순서를 저장하고, 배열 v에 방문 체크와 재귀함수가 끝나면 order에 있던 순서를 뺀다.

// idx 인덱스의 회전연산에 따라 회전
void rotate(int idx){
    // 아래,오른쪽,위,왼쪽(반시계방향)
    // 시계방향으로 움직여야 하기 때문에
    // 값을 받아야 하는 것은 반시계 방향에 있는 것
    int dx[] = {1,0,-1,0};
    int dy[] = {0,1,0,-1};

    int sx,sy,ex,ey;
    // 값 초기화
    sx = info[idx][0] - info[idx][2];
    sy = info[idx][1] - info[idx][2];
    ex = info[idx][0] + info[idx][2];
    ey = info[idx][1] + info[idx][2];
    
    int count = (ex-sx+1)/2; // 반복 횟수
    for(int i = 0; i < count; i++){
        int k = 0;
        
        int x = sx;
        int y = sy;
        int temp = map[x][y]; // 시작 값을 미리 빼둠

        while(k < 4)
        {   
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx == sx && ny == sy) break; // 초기 위치에 돌아오면 종료
            // 정사각형 안에 있을때만
            if((sx <= nx && nx <= ex-i) && (sy <= ny && ny <= ey-i)){
                map[x][y] = map[nx][ny]; // (nx,ny) 값을 (x,y)로 옮김
                x = nx;
                y = ny;
            }
            else k++; // 밖으로 벗어나면 방향 바꿈
        }
        map[sx][sy+1] = temp; // 마지막으로 할당되지 않은 부분에 초기값을 넣음
        // 안쪽 사각형으로 들어감
        sx++;
        sy++;
    }
}

실질적으로 맵을 돌리는 rotate 함수이다.
매개변수로 회전 연산의 번호 인덱스가 들어온다.

여기서 중요하기 봐야 할 것은 회전 방향이 시계방향이 아닌 반시계 방향이라는 점인데,

그 이유는 시계방향으로 움직인다는 것은 해당 위치 관점에서 보면
반시계 방향에 있는 값을 가져오는 것이기 때문이다.

이후 count를 반복 횟수를 위와 같이 설정해 뒀는데 이는 그려보는데 그냥 이렇게 나오더라(...)
그래서 이 반복 횟수만큼 아래 로직을 반복해 준다.

아래 로직은 간단하다.

정사각형 범위 안에 있을 때는 k 방향만큼 쭉 가는데, 범위 밖을 벗어나면 방향을 바꾼다.
그 행위를 쭉 반복하다 처음 지점으로 돌아오면 종료한다.

그리고 그 지점에 초기값을 넣어주고, sx와 sy를 1씩 높여 안쪽 정사각형으로 들어간다.

핵심적인 코드에 대한 설명은 여기까지고, 이제 전체코드를 아래에 올리고 설명을 종료하도록 하겠다.

#include <iostream>
#include <vector>
using namespace std;

int N,M,K;
int ans = INT32_MAX;
int info[6][3];
bool v[6] = {false,};
int origin[51][51];
int map[51][51];
vector<int> order;
int findMin(){
    int minVal = INT32_MAX;
    for(int i = 1; i <= N; i++){
        int val = 0;
        for(int j = 1; j <= M; j++){
            val += map[i][j];
        }
        minVal = min(minVal,val);
    }
    return minVal;
}
// idx 인덱스의 회전연산에 따라 회전
void rotate(int idx){
    // 아래,오른쪽,위,왼쪽(반시계방향)
    // 시계방향으로 움직여야 하기 때문에
    // 값을 받아야 하는 것은 반시계 방향에 있는 것
    int dx[] = {1,0,-1,0};
    int dy[] = {0,1,0,-1};

    int sx,sy,ex,ey;
    // 값 초기화
    sx = info[idx][0] - info[idx][2];
    sy = info[idx][1] - info[idx][2];
    ex = info[idx][0] + info[idx][2];
    ey = info[idx][1] + info[idx][2];
    
    int count = (ex-sx+1)/2; // 반복 횟수
    for(int i = 0; i < count; i++){
        int k = 0;
        
        int x = sx;
        int y = sy;
        int temp = map[x][y]; // 시작 값을 미리 빼둠

        while(k < 4)
        {   
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx == sx && ny == sy) break; // 초기 위치에 돌아오면 종료
            // 정사각형 안에 있을때만
            if((sx <= nx && nx <= ex-i) && (sy <= ny && ny <= ey-i)){
                map[x][y] = map[nx][ny];
                x = nx;
                y = ny;
            }
            else k++; // 밖으로 벗어나면 방향 바꿈
        }
        map[sx][sy+1] = temp; // 마지막으로 할당되지 않은 부분에 초기값을 넣음
        // 안쪽 사각형으로 들어감
        sx++;
        sy++;
    }
}
// 회전 연산의 순서에 대한 모든 경우에 대해 시행
void backTracking(int idx){
    // 회전 연산의 개수를 초과했을 때
    if(idx >= K){
        // 최초의 맵(origin)을 map으로 복사(초기화)
        for(int i = 1; i <= 50; i++)
            for(int j = 1; j <= 50; j++) map[i][j] = origin[i][j];

        // 저장된 회전연산 순서대로 회전 실행
        for(int i = 0; i < order.size(); i++) {
            int tmp = order[i];
            rotate(tmp); // 회전
        }
        
        ans = min(ans,findMin()); // 최솟값 계산
        return;
    }

    // 백트래킹
    for(int i = 0; i < K; i++){
        if(v[i]) continue; // 이미 방문한 곳은 제외
        v[i] = true; // 방문 처리
        order.push_back(i); // 순서대로 담음
        backTracking(idx+1); // 다음 함수 호출
        order.pop_back(); // 호출 종료시 담아뒀던 그 인덱스 제거
        v[i] = false; // 방문 처리 해제
    }
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> N >> M >> K;

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++) cin >> origin[i][j];
    }
    for(int i = 0; i < K; i++){
        int v1,v2,v3;
        cin >> v1 >> v2 >> v3;
        info[i][0] = v1;
        info[i][1] = v2;
        info[i][2] = v3;
    }
    backTracking(0);
    cout << ans;

}

 

 

---

시행착오

백트래킹으로 풀어야 한다는 아이디어까지는 떠올리고 구현할 수 있었다.
하지만 배열 돌리기 구현을 실패했다.

나는 배열 전체를 탐색해서 돌리는 방식을 선택했는데,
그 방식이 오히려 더 복잡했고, 무엇보다 맵을 복사하는 방식을 선택하지 않았다.

그 방식이 시간초과를 초래할 것이라는 생각 때문에 시도를 안 했다.

그리고 저런 식으로 BFS처럼 하는 방식도 생각했지만
솔직히 내가 잘 안 쓰는 방식이기도 하고 자신 없어서 안 했는데,
이제 저런 방식을 많이 써야 한다는 것을 깨달았다.