[틀림] 백준 17406번 : 배열 돌리기 4 // 배열회전은 rotate 활용, 1차원에서 생각하라

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;
}

저작자표시

'Algorithm > 구현' 카테고리의 다른 글

[알고리즘] 백준 12100 Easy // 구현, 대칭구현은 한방향만 만들고 배열회전을 이용하라 (0)	2025.02.10
[알고리즘] 백준 14890 경사로 // 구현, 전치행렬이용, cnt 이용법 (0)	2025.01.11
백준 14719 빗물 c++ // 구현, 그리디 (0)	2024.05.14
프로그래머스 귤고르기 c++ // 공간복잡도 공식, 구현 (0)	2024.03.28
프로그래머스 달리기경주 c++ // 해쉬맵 기본정렬됨(키값기준오름차순), 구현 (0)	2024.03.27

* 순열

* 25.2.13. 2회독

'Algorithm > 구현' 카테고리의 다른 글

티스토리툴바