[C++] 백준(BOJ) - 17406 : 배열 돌리기 4
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.
1 2 3
2 1 1
4 5 6
배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.
예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.
회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.
배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.
입력
첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.
둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.
출력
배열 A의 값의 최솟값을 출력한다.
알고리즘
- 순열_permutation
- 구현
풀이
- 순서에 따라 다르다 -> 순열을 생각
- idx만을 저장해서 원하는 순열 조합을 만들어 내기
- 원본배열을 건드리지 않고 각 케이스를 행했을 때, min 값을 계산하기 위한 임시벡터 사용
- 회전배열 구현
- 기준 지점을 잡기 (sy, sx, ey, ex)
- 기준 지점에 도달 했을 때, 방향벡터 전환
pair<int,int>를 활용하여 위치값의 (y,x) 값만 빼내고, 담긴 값은 새로운 배열을 활용하여 회전 시키는 아이디어
코드
// BOJ-17460 : 배열 돌리기4
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
const int dy[] = { 0,1,0,-1 };
const int dx[] = { 1,0,-1,0 };
int n, m, k, r, c, s, res = INF, sy, sx, ey, ex, dir;
int a[54][54], b[54][54], visited[54][54];
vector<int> v_idx; // 회전배열을 뽑는 순열을 담는 벡터
struct A {
int y, x, cnt;
};
vector<A> v; // 회전배열
vector<pair<int, int>> vv; // 회전하는 배열 (y,x) 위치값 담기는 배열
void go(int y, int x, int first)
{
if (!first && y == sy && x == sx) dir++; // 기준지점 도달 시 방향전환
if (!first && y == sy && x == ex) dir++;
if (!first && y == ey && x == ex) dir++;
if (!first && y == ey && x == sx) dir++;
int ny = y + dy[dir];
int nx = x + dx[dir];
if (visited[ny][nx]) return;
visited[ny][nx] = 1;
vv.push_back({ ny,nx });
go(ny, nx, 0);
}
void rotateAll(int y, int x, int cnt)
{
for (int i = 1; i <= cnt; i++)
{
// 기준 지점
sy = y - 1 * i;
sx = x - 1 * i;
ey = y + 1 * i;
ex = x + 1 * i;
// 부분구역이 달라지면 위치배열, 방향벡터 및 방문 처리 배열 초기화
vv.clear();
dir = 0;
memset(visited, 0, sizeof(visited));
visited[sy][sx] = 1;
vv.push_back({ sy,sx });
go(sy, sx, 1);
vector<int> vvv; // 부분구역의 Rotate를 위한 임시 벡터 (벡터 회전을 위해 rotate 함수를 쓰기 위해 vector<int> 형 임시 벡터 선언)
for (pair<int, int> c : vv) vvv.push_back(b[c.first][c.second]);
//rotate(vvv.begin(), vvv.begin() + v.size() - 1, vvv.end());
rotate(vvv.rbegin(), vvv.rbegin() + 1, vvv.rend()); // 벡터 오른쪽 회전
for (int i = 0; i < vv.size(); i++)
{
b[vv[i].first][vv[i].second] = vvv[i];
}
}
}
int solve()
{
for (int i : v_idx) rotateAll(v[i].y, v[i].x, v[i].cnt); // 뽑힌 회전배열에 따라 돌리기
int mn = INF;
for (int i = 0; i < n; i++)
{
int cnt = 0;
for (int j = 0; j < m; j++) cnt += b[i][j];
mn = min(mn, cnt);
}
return mn;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> a[i][j];
}
}
for (int i = 0; i < k; i++)
{
cin >> r >> c >> s;
r--;
c--;
v.push_back({ r,c,s });
v_idx.push_back(i);
}
do {
memcpy(b, a, sizeof(b));
res = min(res, solve());
} while (next_permutation(v_idx.begin(), v_idx.end()));
cout << res << '\n';
return 0;
}
평가
- idx를 활용해서 전체 순열을 뽑아내는 아이디어
- 임시벡터 b를 활용하여 원본배열 a를 건드리지 않고 min 값을 계산
- 기준 지점을 잡고, 기준 지점에 도달하였을 때, 방향 벡터를 전환하는 방식으로 회전 구현
- 회전 배열의 경우 인덱스 값을
pair<int,int>형식으로 저장하고 있다vector<int>의rotate함수를 활용하여 벡터 오른쪽 회전 구현 - 간단한 구현 문제이지만 여러 개의 임시 벡터를 활용하여 원하는 기능을 동작하게 하는 연습을 꾸준히 해야 함
