백준 17406번) 배열 돌리기 4 (JAVA)

알고리즘 문제

백준 17406번) 배열 돌리기 4 (JAVA)

roder 2022. 8. 11. 13:12

https://www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의

www.acmicpc.net

#문제

크기가 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[1][1]   A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
             ↑                                       ↓
A[2][1]   A[2][2]   A[2][3] → A[2][4] → A[2][5]   A[2][6]
             ↑         ↑                   ↓         ↓
A[3][1]   A[3][2]   A[3][3]   A[3][4]   A[3][5]   A[3][6]
             ↑         ↑                   ↓         ↓
A[4][1]   A[4][2]   A[4][3] ← A[4][4] ← A[4][5]   A[4][6]
             ↑                                       ↓
A[5][1]   A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]

A[6][1]   A[6][2]   A[6][3]   A[6][4]   A[6][5]   A[6][6]

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.


배열 A	(3, 4, 2) 연산 수행 후	(4, 2, 1) 연산 수행 후

배열 A	(4, 2, 1) 연산 수행 후	(3, 4, 2) 연산 수행 후

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

#알고리즘

구현

완전탐색

백트래킹

#풀이방법

순열을 이용하여 돌리는 순서를 탐색하고, 배열 돌리는 것을 구현하여 그 안에서 최솟값을 찾으면 되는 문제이다.

순열을 이용하는 것은 어렵지 않지만, 배열을 돌리는 것에 많은 시간이 걸렸다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
          
            if (depth == r) {
                simul(output);
                return;
            }
 
            for (int i = 0; i < n; i++) {
                
                if (visited[i] != true) {
                    
                    visited[i] = true;
                    output[depth] = arr[i];
                    perm(arr, output, visited, depth + 1, n, r);
                    visited[i] = false;
                    
                }
                
            }
            
      }
Colored by Color Scripter
cs

순열 메소드를 구글링하여 output에 순서를 넣은 후, simul 메소드를 호출하여 시뮬레이션을 돌린다.

(여기까지는 어렵지 않다.)

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 public static void simul(int[] output) {
          
          int[][] temp = new int[N][M];
          
          for(int i=0; i<N; i++) {
              for(int j=0; j<M; j++) {
                  temp[i][j] = arr[i][j];
              }
          }//temp 배열 복사  
          
          //단순히 temp = arr을 하게되면 temp배열이 output에 영향을 주어 output까지 값이 바뀌게 된다.
        
          
          for(int i=0; i<output.length; i++) {
              
              int r = rotation[output[i]][0];
              int c = rotation[output[i]][1];
              int s = rotation[output[i]][2];
              
              //output의 랜덤 값을 따라 r,c,s를 분배한다. 
              
              rot(temp,r-s,c-s,r-s,c+s,r+s,c-s,r+s,c+s);
              //rot 메소드를 호출하여 주어진 순서대로 배열을 돌림
          
          }
          
          for(int i=0; i<temp.length; i++) {
              
              int sum = 0;
              
              for(int j=0; j<temp[0].length; j++)
                  sum += temp[i][j];
              
              if(sum < min)
                  min = sum;
              
              //각 행마다 행을 더해주어 최솟값을 계산한다.
          }
         
          
      }
Colored by Color Scripter
cs

매개변수로 받은 ouput을 기준으로 rot 메소드를 호출하여 계속하여 배열을 돌려준다.

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
26
27
28
29
 public static    void rot(int[][] temp, int leftTopY, int leftTopX ,int rightTopY, int rightTopX,
              int leftDownY, int leftDownX, int rightDownY, int rightDownX){
            
          if(leftTopX == rightTopX && leftTopY == rightTopY)
              return;//2가지 좌표가 같으면 return
          
          int init_num = temp[leftTopY][leftTopX];
          
          for(int i=leftTopY; i<leftDownY; i++) {
              temp[i][leftTopX] = temp[i+1][leftTopX];
          }//1
          
          for(int i = leftDownX; i<rightDownX; i++) {
              temp[leftDownY][i] = temp[leftDownY][i+1];
          }//2
          
          for(int i = rightDownY; i>rightTopY; i--) {
              temp[i][rightDownX] = temp[i-1][rightDownX];
          }//3
          
          for(int i = rightTopX; i>leftTopX; i--) {
              temp[rightTopY][i] = temp[rightTopY][i-1];
          }//4
          
          temp[leftTopY][leftTopX+1] = init_num;
          
          rot(temp,leftTopY+1,leftTopX+1,rightTopY+1,rightTopX-1,leftDownY-1,leftDownX+1,rightDownY-1,rightDownX-1);
         
      }//돌리기 구현
Colored by Color Scripter
cs

여기서 돌리는 구현 부분이 좀 까다롭긴 하지만 매개변수를

(int leftTopY, int leftTopX ,int rightTopY, int rightTopX,

int leftDownY, int leftDownX, int rightDownY, int rightDownX)

로 나눠 한바퀴를 돌려 준 후, 4지점을 재조정하여 다시 재호출한다.

그렇게 모든 지점의 점이 같을 경우 return해주어 메소드를 종료시켜준다.

#전체 코드

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import java.util.*;
//1t,돌리는 것을 구현해야함
//완전탐색, 순열
 
public class Main {
 
    static int N;
    static int M;
    static int K;
    static int[][] arr;
    static int[][] rotation;
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();
        
        rotation = new int[K][3];
        arr = new int[N][M];
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                arr[i][j] = sc.nextInt();
            }
        }//배열 입력 받기
        
        
        for(int i=0; i<rotation.length; i++) {
            
            rotation[i][0] = sc.nextInt()-1;
            rotation[i][1] = sc.nextInt()-1;
            rotation[i][2] = sc.nextInt();
            
        }
        
        boolean[] visited = new boolean[K];
        int[] arr = new int[K];
        
        for(int i=0; i<arr.length; i++)
            arr[i] = i;
        
        int[] output = new int[K];
        
        perm(arr,output,visited,0,K,K);
        
        System.out.println(min);
        
        
    }
    
      static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
          
            if (depth == r) {
                simul(output);
                return;
            }
 
            for (int i = 0; i < n; i++) {
                
                if (visited[i] != true) {
                    
                    visited[i] = true;
                    output[depth] = arr[i];
                    perm(arr, output, visited, depth + 1, n, r);
                    visited[i] = false;
                    
                }
                
            }
            
      }
      
      
      public static void simul(int[] output) {
          
          int[][] temp = new int[N][M];
          
          for(int i=0; i<N; i++) {
              for(int j=0; j<M; j++) {
                  temp[i][j] = arr[i][j];
              }
          }//temp 배열 복사  
          
          //단순히 temp = arr을 하게되면 temp배열이 output에 영향을 주어 output까지 값이 바뀌게 된다.
        
          
          for(int i=0; i<output.length; i++) {
              
              int r = rotation[output[i]][0];
              int c = rotation[output[i]][1];
              int s = rotation[output[i]][2];
              
              //output의 랜덤 값을 따라 r,c,s를 분배한다. 
              
              rot(temp,r-s,c-s,r-s,c+s,r+s,c-s,r+s,c+s);
              //rot 메소드를 호출하여 주어진 순서대로 배열을 돌림
          
          }
          
          for(int i=0; i<temp.length; i++) {
              
              int sum = 0;
              
              for(int j=0; j<temp[0].length; j++)
                  sum += temp[i][j];
              
              if(sum < min)
                  min = sum;
              
              //각 행마다 행을 더해주어 최솟값을 계산한다.
          }
         
          
      }
      
      public static    void rot(int[][] temp, int leftTopY, int leftTopX ,int rightTopY, int rightTopX,
              int leftDownY, int leftDownX, int rightDownY, int rightDownX){
            
          if(leftTopX == rightTopX && leftTopY == rightTopY)
              return;//2가지 좌표가 같으면 return
          
          int init_num = temp[leftTopY][leftTopX];
          
          for(int i=leftTopY; i<leftDownY; i++) {
              temp[i][leftTopX] = temp[i+1][leftTopX];
          }//1
          
          for(int i = leftDownX; i<rightDownX; i++) {
              temp[leftDownY][i] = temp[leftDownY][i+1];
          }//2
          
          for(int i = rightDownY; i>rightTopY; i--) {
              temp[i][rightDownX] = temp[i-1][rightDownX];
          }//3
          
          for(int i = rightTopX; i>leftTopX; i--) {
              temp[rightTopY][i] = temp[rightTopY][i-1];
          }//4
          
          temp[leftTopY][leftTopX+1] = init_num;
          
          rot(temp,leftTopY+1,leftTopX+1,rightTopY+1,rightTopX-1,leftDownY-1,leftDownX+1,rightDownY-1,rightDownX-1);
         
      }//돌리기 구현
      
 
}
Colored by Color Scripter
cs

'알고리즘 문제' 카테고리의 다른 글

프로그래머스) 방금 그곡 (JAVA) (0)	2022.09.05
프로그래머스) 단체사진 찍기 (0)	2022.08.12
백준 16637번) 괄호 추가하기(JAVA) (0)	2022.08.10
백준 17142번) 연구소3(JAVA) (0)	2022.08.05
프로그래머스) 튜플 (0)	2022.08.02

현재글백준 17406번) 배열 돌리기 4 (JAVA)

다시 보려고 만든 개발로그

개발 , 알고리즘 문제 정리 사이트

Today :
Yesterday :

다시 보려고 만든 개발로그