코딩테스트/그래프|트리
[DFS 순열] 백준 17406 배열 돌리기 4 C++
유(YOO)
2022. 2. 5. 22:12
※ 문제
https://www.acmicpc.net/problem/17406
※ 풀이
1) 회전 연산은 모두 한 번씩 사용해야하며 순서는 바꿔도 상관없으므로 DFS를 이용해 연산 순서 순열을 구한다.
2) DFS로 구한 연산 순서로 최솟값을 구한 후, 배열을 원래대로 바꿔야 다음 연산 순서를 계속해서 진행할 수 있다.
3) 회전 연산은 간격을 1부터 s까지 왼쪽 위부터 반시계 방향으로 회전시킨다.
#include <bits/stdc++.h>
using namespace std;
int n, m, k, ans = INT_MAX;
int arr[52][52], temp[52][52], R[6], C[6], S[6], order[6];
bool visited[6];
void calMin() {
for (int i = 1; i <= n; i++) {
int minNum = 0;
for (int j = 1; j <= m; j++) {
minNum += arr[i][j];
}
ans = min(ans, minNum);
}
}
void rotate(int r, int c, int s) {
for (int j = 1; j <= s; j++) {
int start = arr[r - j][c - j]; // s 아니고 j
// 반시계
for (int i = r - j; i < r + j; i++) arr[i][c - j] = arr[i + 1][c - j];
for (int i = c - j; i < c + j; i++) arr[r + j][i] = arr[r + j][i + 1];
for (int i = r + j; i > r - j; i--) arr[i][c + j] = arr[i - 1][c + j];
for (int i = c + j; i > c - j; i--) arr[r - j][i] = arr[r - j][i - 1];
arr[r - j][c - j + 1] = start;
}
}
void dfs(int depth) {
if (depth == k) {
for (int i = 1; i <= n; i++) { // 배열 임시 저장
for (int j = 1; j <= m; j++) {
temp[i][j] = arr[i][j];
}
}
for (int i = 0; i < k; i++) { // 회전
int idx = order[i];
rotate(R[idx], C[idx], S[idx]);
}
calMin(); // 최솟값 계산
for (int i = 1; i <= n; i++) { // 배열 원래대로 복원
for (int j = 1; j <= m; j++) {
arr[i][j] = temp[i][j];
}
}
return;
}
for (int i = 0; i < k; i++) {
if (visited[i]) continue;
visited[i] = true;
order[depth] = i; // 회전 연산 순서
dfs(depth + 1);
visited[i] = false;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
}
}
for (int i = 0; i < k; i++) {
cin >> R[i] >> C[i] >> S[i];
}
dfs(0);
cout << ans;
}