백준 17406번 배열 돌리기4 C++ 백트래킹, 구현, 시뮬레이션

리뷰

 

완전 탐색을 통해 배열을 돌리는 경우의 수를 모두 실행하고 최적값을 찾는 문제

회전을 하는 횟수인 k의 범위가 6으로 작아서 완전 탐색을 돌려도 시간이 크게 많이 걸리지는 않았다.

 

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

 

문제 풀이

1. input 함수를 통해 n, m, k값을 입력 받고 2차 배열 정보를 받아준다.
2. k번에 걸쳐 회전을 할 좌표를 받고, 회전할 범위를 받은 뒤 구조체 배열 pos에 전달해 준다.
3. 좌표 인덱스를 받을 빈 벡터 path를 초기화 해주고, dfs 함수의 매개변수로 0과 path를 전달해 준다.
4. dfs 함수를 통해 k! 개의 경우의 수를 구해준다. 매번 방문 처리 후 path에 회전할 순서를 저장해 주면 된다.
5. 재귀가 k번째에 달했을때 simul 함수에 path와 flag를 전달해 주었다.
6. simul 함수를 통해 path에 저장된 배열 회전 순서를 spin_sqr 함수에 전달해 준다. flag는 1이면 돌리기, 0이면 원상복구이다.
7. spin_sqr은 회전시킬 범위를 s를 통해 줄여주며 각 범위에 해당하는 외곽을 bfs함수를 통해 배열을 돌려준다.
8. bfs를 통해 시작 좌표에서 출발해 다시 시작 좌표로 돌아올 때까지 배열을 회전시켜 준다.
9. 배열 회전이 완료되었다면, 각 행을 탐색하여 최소값을 찾은 뒤 ans배열에 최소값을 최신화 해준다.
10. 이후 돌려놨던 배열을 flag를 0으로 전달하여 다시 원상복구 시켜준 뒤 return 처리 해준다.
11. 모든 탐색을 완료한 뒤 ans 변수에 저장된 값을 출력해 주면 된다.

 

참고 사항

simul함수에서 배열을 원상태로 돌려놓을때는 path배열을 반대로 탐색해 주어야 한다.

사실상 k길이 만큼 모두 회전시켜줄 필요는 없어 보이지만 그정도까지 최적화는 하기 힘들 것 같아서 패스

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;
int n, m, k, ans = 1e9;
int lst[51][51];

int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int v[6] = { 0, };

struct Pos {
    int tx, ty, bx, by, s;
};

struct Sim {
    int x, y, d;
};

Pos pos[6];

void input() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> lst[i][j];
        }
    }
    for (int i = 0; i < k; i++) {
        int a, b, c; cin >> a >> b >> c;
        pos[i] = { a - c, b - c, a + c, b + c, c };
    }
}

void bfs(int sx, int sy, int ex, int ey, int dir, int turn) {
    queue<Sim> q;
    q.push({ sx, sy, dir });

    while (!q.empty()) {
        Sim sim = q.front(); q.pop();
        int cx = sim.x, cy = sim.y, cd = sim.d;
        int nx = cx + dx[cd], ny = cy + dy[cd];
        if (sx <= nx && nx <= ex && sy <= ny && ny <= ey) {
            if (nx == sx && ny == sy) return;
            swap(lst[sim.x][sim.y], lst[nx][ny]);
            q.push({ nx, ny, cd });
        }
        else {
            q.push({ sim.x, sim.y, (cd + turn) % 4 });
        }
    }
}

void spin_sqr(int tx, int ty, int bx, int by, int s, int dir, int turn) {
    for (int i = 0; i < s; i++) {
        bfs(tx + i, ty + i, bx - i, by - i, dir, turn);
    }
}

void simul(vector<int>& path, int flag) {
    if (flag) {
        for (int i = 0; i < k; i++) {
            Pos now = pos[path[i]];
            spin_sqr(now.tx, now.ty, now.bx, now.by, now.s, 1, 3);
        }
    }
    else {
        for (int i = k - 1; i >= 0; i--) {
            Pos now = pos[path[i]];
            spin_sqr(now.tx, now.ty, now.bx, now.by, now.s, 0, 1);
        }
    }
}

int chk() {
    int min_val = 1e9;
    for (int i = 1; i <= n; i++) {
        int row_val = 0;
        for (int j = 1; j <= m; j++) {
            row_val += lst[i][j];
        }
        min_val = min(min_val, row_val);
    }
    return min_val;
}

void dfs(int level, vector<int>& path) {
    if (level == k) {
        simul(path, 1);
        ans = min(ans, chk());
        simul(path, 0);
        return;
    }

    for (int i = 0; i < k; i++) {
        if (v[i]) continue;
        v[i] = 1;
        path.push_back(i);
        dfs(level + 1, path);
        path.pop_back();
        v[i] = 0;
    }
}

int main() {
    input();
    vector<int> path;
    dfs(0, path);
    cout << ans;
}