Algorithm/구현
[틀림] 백준 17406번 : 배열 돌리기 4 // 배열회전은 rotate 활용, 1차원에서 생각하라
Mini_96
2022. 8. 10. 17:22
https://www.acmicpc.net/problem/17406
17406번: 배열 돌리기 4
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의
www.acmicpc.net
* 순열
public static void permutation(int idx, int k) {
if(idx == k) {
//완성배열으로 할일(static result에 완성되있음)
return;
}
for(int i = 0; i < k; i++) {
if(visited[i] == false) {
visited[i] = true;
//방문처리를 지그재그로(visit0=true, visit1=true)
//i=0) visit[0]=true -perm(1,2)i=1(방문안된것만방문) visit1=true -perm(2,2)return
//i=1) visit[1]=true ...
//i=2) visit[2]=true ...
result[idx] = i; //idx는 1씩결과는 항상 앞부터 채움 =>순열make
permutation(idx + 1, k);
visited[i] = false; //리턴되면서 다 방문안함 처리
}
}
}
result 0 1
1 0
visit t(1) t(2)
t(2) t(1번째)
import java.util.*;
public class Main_17406_유동훈_2 {
static int[][] board;
static int[][] rotation;
static int min = Integer.MAX_VALUE;
static int n, m;
static boolean[] visited;
static int[] result;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
int k = scan.nextInt();
board = new int[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
board[i][j] = scan.nextInt();
}
}
rotation = new int[k][3];
for(int i = 0; i < k; i++) {
rotation[i][0] = scan.nextInt();
rotation[i][1] = scan.nextInt();
rotation[i][2] = scan.nextInt();
}
visited = new boolean[k];
result = new int[k];
permutation(0, k);
System.out.println(min);
}
public static void permutation(int idx, int k) {
if(idx == k) {
int[][] copy = new int[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
copy[i][j] = board[i][j];
}
}
findMin(copy); //완료(result완성했음)->다음만들기전에 할일:findMin
return;
}
for(int i = 0; i < k; i++) {
if(visited[i] == false) {
visited[i] = true;
//방문처리를 지그재그로(visit0=true, visit1=true)
//i=0) visit[0]=true -perm(1,2)i=1(방문안된것만방문) visit1=true -perm(2,2)return
//i=1) visit[1]=true ...
//i=2) visit[2]=true ...
result[idx] = i; //idx는 1씩결과는 항상 앞부터 채움 =>순열make
permutation(idx + 1, k);
visited[i] = false; //리턴되면서 다 방문안함 처리
}
}
}
public static void findMin(int[][] copy) {
for(int i = 0; i < result.length; i++) {
int lx = rotation[result[i]][0] - rotation[result[i]][2] - 1;
int ly = rotation[result[i]][1] - rotation[result[i]][2] - 1;
int rx = rotation[result[i]][0] + rotation[result[i]][2] - 1;
int ry = rotation[result[i]][1] + rotation[result[i]][2] - 1;
rotate(lx, ly, rx, ry, copy); //lx ly ~ rx ry까지 회전
}
rowcal(copy);//회전한 배열의 최소 행값을 구함
}
public static void rowcal(int[][] copy) {
for(int i = 0; i < copy.length; i++) {
int sum = 0;
for(int j = 0; j < copy[i].length; j++) {
sum += copy[i][j];
}
min = Math.min(min, sum);
}
}
/*
* @param
* lx=좌x,ly=좌y ....
*/
public static void rotate(int lx, int ly, int rx, int ry, int[][] copy) {
if(lx == rx && ly == ry) {
return;
}
int[] temp = new int[3]; //방향별로 값을 옮기다 보면 지워질 수 있는 좌표값을 저장.
temp[0] = copy[lx][ry];
temp[1] = copy[rx][ry];
temp[2] = copy[rx][ly];
//오른쪽으로 회전
for(int i = ry; i > ly; i--) {
copy[lx][i] = copy[lx][i - 1];
}
//아래로 회전
for(int i = rx; i > lx; i--) {
if(i == lx + 1) copy[i][ry] = temp[0];
else copy[i][ry] = copy[i - 1][ry];
}
//왼쪽으로 회전
for(int i = ly; i < ry; i++) {
if(i == ry - 1) copy[rx][i] = temp[1];
else copy[rx][i] = copy[rx][i + 1];
}
//위로 회전
for(int i = lx; i < rx; i++) {
if(i == rx - 1) copy[i][ly] = temp[2];
else copy[i][ly] = copy[i + 1][ly];
}
rotate(lx + 1, ly + 1, rx - 1, ry - 1, copy);
}
}
* 25.2.13. 2회독
- 핵심 아이디어
- vv에 대상좌표들을 담기
- vvv에 값들을 담기
- 좌표, 값을 분리해서 저장하라!
- 3. 회전이해
- 1차원으로 펼쳐봐라
- 뒤로땡김 -> pivot이 뒤에있기
- rotate(begin, begin+size-1, end)
- 결론 : 값을 밀고 좌표에 대입하면됨
- 1.5 for(int i=1; i<=cnt) 이해
- 중심점(r,c)에서 시작점을 좌측위로 한칸씩 이동하는 로직임
// 예시 5x5 배열
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
// 중심점 (2,2), cnt=2 일 때
// i=1 일 때 (바깥쪽 테두리)
sy = 2 - 1 = 1
sx = 2 - 1 = 1
ey = 2 + 1 = 3
ex = 2 + 1 = 3
// 따라서 아래 숫자들이 회전됨 (시계 방향):
7 8 9
12 14
17 18 19
// i=2 일 때 (안쪽 테두리)
sy = 2 - 2 = 0
sx = 2 - 2 = 0
ey = 2 + 2 = 4
ex = 2 + 2 = 4
// 바깥쪽 테두리의 숫자들이 회전됨:
1 2 3 4 5
6 10
11 15
16 20
21 22 23 24 25
- 나의코드 (학습후 구현)
#include<bits/stdc++.h>
using namespace std;
#define s second
#define f first
// 최댓값 설정 (최솟값을 찾기 위한 초기값)
const int INF = 987654321;
// 방향 배열 (우, 하, 좌, 상)
const int dy[] = {0, 1, 0, -1};
const int dx[] = {1, 0, -1, 0};
// 전역 변수 선언
int n, m, k; // n: 배열 세로크기, m: 배열 가로크기, k: 회전 연산의 개수
int a[104][104]; // 원본 배열
int b[104][104]; // 회전 연산을 수행할 임시 배열
int ret = INF; // 결과값 (각 행의 합 중 최솟값)
int r, c, s; // r,c: 회전의 중심점, s: 회전의 크기
int visited[104][104]; // 방문 체크 배열
int dir; // 현재 진행 방향
int sy, sx, ey, ex; // 현재 회전할 영역의 시작점(sy,sx)과 끝점(ey,ex)
// 회전 연산 좌표를 저장할 벡터
vector<pair<int, int>> vv;
// 회전 연산의 순서를 저장할 벡터
vector<int> v_idx;
// 회전 연산 정보를 저장할 구조체
struct A{
int y, x, cnt; // y,x: 중심점, cnt: 회전 크기
};
vector<A> v;
// 회전을 수행하는 재귀 함수 (회전 대상 좌표들을 vv에 넣기)
void go(int y, int x, int first){
//모서리라면 방향을 바꿔야함
if(!first && y==sy && x==ex) dir++; // 우측위모서리
if(!first && y==ey && x==ex) dir++; // 우측아래 모서리
if(!first && y==ey && x==sx) dir++; //좌측아래 모서리
if(!first && y==sy && 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){
//중심점(y,x)로부터 start(왼위), end(오아) 구하기, 중심으로부터 점차 밖으로 확장해나감
for(int i=1;i<=cnt;++i) {
sy=y - 1*i;
sx=x - 1*i; //[틀림] start, end는 전역변수임에 주의!!
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; // 체크된 값들을 저장
for(auto p : vv) { //vv에는 체크된 좌표들이 담겨있음
vvv.push_back(b[p.first][p.second]);
}
//[틀림] 값을 뒤로밀기!!!!!!!!!! (좌표아님!!)
rotate(vvv.begin(), vvv.begin()+vvv.size()-1,vvv.end());
for(int i=0;i<vv.size();++i) { //vv에는 체크된 좌표들이 담겨있음(한칸 회전후)
b[vv[i].first][vv[i].second] = vvv[i]; //이동된 좌표에 원본값을 넣기
}
}
}
// 현재 순열에 대해 회전 연산을 수행하고 결과를 반환하는 함수
int solve(){
// 현재 순열 순서대로 회전 연산 수행
for(auto i : v_idx) {
rotateAll(v[i].y,v[i].x,v[i].cnt);
}
// 각 행의 합 중 최솟값 계산
int _ret = INF;
for(int i = 0; i < n; i++){
int cnt = 0;
for(int j = 0; j < m; j++) cnt += b[i][j];
_ret = min(_ret, cnt);
}
return _ret;
}
int main(){
// 입력
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--; // 0-based 인덱스로 변환
v.push_back({r, c, s});
v_idx.push_back(i);
}
// 모든 가능한 회전 연산 순서에 대해 시도
do{
// 원본 배열 복사
memcpy(b,a,sizeof(a)); //a를 b에 복사
// 현재 순열에 대한 결과와 비교하여 최솟값 갱신
ret = min(ret, solve());
}while(next_permutation(v_idx.begin(), v_idx.end()));
// 결과 출력
cout << ret << "\n";
return 0;
}- 원본코드 (큰돌)
#include<bits/stdc++.h>
using namespace std;
#define s second
#define f first
// 최댓값 설정 (최솟값을 찾기 위한 초기값)
const int INF = 987654321;
// 방향 배열 (우, 하, 좌, 상)
const int dy[] = {0, 1, 0, -1};
const int dx[] = {1, 0, -1, 0};
// 전역 변수 선언
int n, m, k; // n: 배열 세로크기, m: 배열 가로크기, k: 회전 연산의 개수
int a[104][104]; // 원본 배열
int b[104][104]; // 회전 연산을 수행할 임시 배열
int ret = INF; // 결과값 (각 행의 합 중 최솟값)
int r, c, s; // r,c: 회전의 중심점, s: 회전의 크기
int visited[104][104]; // 방문 체크 배열
int dir; // 현재 진행 방향
int sy, sx, ey, ex; // 현재 회전할 영역의 시작점(sy,sx)과 끝점(ey,ex)
// 회전 연산 좌표를 저장할 벡터
vector<pair<int, int>> vv;
// 회전 연산의 순서를 저장할 벡터
vector<int> v_idx;
// 회전 연산 정보를 저장할 구조체
struct A{
int y, x, cnt; // y,x: 중심점, cnt: 회전 크기
};
vector<A> v;
// 회전을 수행하는 재귀 함수
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){
// 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;
for(pair<int, int> c : vv) vvv.push_back(b[c.f][c.s]);
// 실제 회전 수행 (마지막 원소를 첫 번째로 이동)
rotate(vvv.begin(), vvv.begin() + vvv.size() - 1, vvv.end());
// 회전된 값들을 배열에 다시 저장
for(int i = 0; i < vv.size(); i++) b[vv[i].f][vv[i].s] = vvv[i];
}
}
// 현재 순열에 대해 회전 연산을 수행하고 결과를 반환하는 함수
int solve(){
// 현재 순열 순서대로 회전 연산 수행
for(int i : v_idx) rotateAll(v[i].y, v[i].x, v[i].cnt);
// 각 행의 합 중 최솟값 계산
int _ret = INF;
for(int i = 0; i < n; i++){
int cnt = 0;
for(int j = 0; j < m; j++) cnt += b[i][j];
_ret = min(_ret, cnt);
}
return _ret;
}
int main(){
// 입력
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--; // 0-based 인덱스로 변환
v.push_back({r, c, s});
v_idx.push_back(i);
}
// 모든 가능한 회전 연산 순서에 대해 시도
do{
// 원본 배열 복사
memcpy(b, a, sizeof(b));
// 현재 순열에 대한 결과와 비교하여 최솟값 갱신
ret = min(ret, solve());
}while(next_permutation(v_idx.begin(), v_idx.end()));
// 결과 출력
cout << ret << "\n";
return 0;
}