[백준] 17406 - 배열 돌리기4

삼성전자 상시테스트 문제와 상당히 유사하다고 해서 풀어보았는데..... 돌리는게 귀찮은 문제라고 결론을 내려본다

단순히 dfs로 돌리는 순서를 정해주면서, 최소값을 찾는 배열을 만들어 주느냐가 관건이다

항상 말하지만 나는 stl을 안쓰고 짜는 것을 선호하지만, 이 문제는 색종이 붙이기와 같이 dfs함수가 return되었을 때 map이 그 depth에서 만든 map으로 원복되는 것을 원하기 때문에 vector를 선언해서 사용했다

1. map을 선언하고, map을 rotation시키는 좌표를 입력받는다

2. dfs로 전체 탐색 하면서, 순서를 저장하는 것이 아닌, 그때마다 돌려준다.

- 저장했다 한번에 돌려줘도 되지만, 비효율적이라고 생각이 들었기 때문

3. depth가 K에 이르면, 문제의 조건에 따른 각 행의 합의 최소값을 답으로 갱신

#include <iostream>
#include <vector>
#define INF 987654321
using namespace std;
 
struct ROT {
    int y, x, s;
}arr[10];
 
bool visit[10];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };
int N, M, K, dab = INF;
 
void rotate(const ROT rot, vector<vector<int> > &map) {
    const int s = rot.s;
    const int y = rot.y - 1;
    const int x = rot.x - 1;
    for (int k = 1; k <= s; k++) {
        int x_ = x - k;
        int y_ = y - k;
        int tmp = map[y_][x_];
        int dir = 0;
        int input;
        do {
            int nx = x_ + dx[dir];
            int ny = y_ + dy[dir];
            input = tmp;
            tmp = map[ny][nx];
            map[ny][nx] = input;
            x_ = nx; y_ = ny;
            if (x_ == x + k && y_ == y - k) dir = 1;
            if (x_ == x + k && y_ == y + k) dir = 2;
            if (x_ == x - k && y_ == y + k) dir = 3;
        } while (x_ != x - k || y_ != y - k);
    }
}
 
void dfs(int d, int oper, vector<vector<int> > map) {
    if (oper != -1) rotate(arr[oper], map);
    if (d == K) {
        for (int i = 0; i < N; i++) {
            int tmp = 0;
            for (int j = 0; j < M; j++)
                tmp += map[i][j];
            dab = tmp > dab ? dab : tmp;
        }
        return;
    }
    for (int i = 0; i < K; i++) {
        if (visit[i]) continue;
        visit[i] = true;
        dfs(d + 1, i, map);
        visit[i] = false;
    }
}
 
int main(void) {
    cin >> N >> M >> K;
    vector<vector<int> > map(N, vector<int>(M, 0));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> map[i][j];
    for (int i = 0; i < K; i++)
        cin >> arr[i].y >> arr[i].x >> arr[i].s;
    dfs(0, -1, map);
    cout << dab << endl;
    return 0;
}