문제 링크:
난이도: 골드 4
소요시간: 1시간 20분
문제:
크기가 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의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.
배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.
입력:
첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.
둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.
출력:
배열 A의 값의 최솟값을 출력한다.
제한:
- 3 ≤ N, M ≤ 50
- 1 ≤ K ≤ 6
- 1 ≤ A[i][j] ≤ 100
- 1 ≤ s
- 1 ≤ r-s < r < r+s ≤ N
- 1 ≤ c-s < c < c+s ≤ M
문제 이해:
작성자는 문제 이해가 오래걸렸다.
한 행렬과 회전 횟수가 주어졌을때 회전 결과 행렬에서 가장 작은 행 값이 최소가 되는 값을 구하는 문제이다.
이해하기 쉽게 예제입력 1을 예를 들어보며 설명한다.
5 6 2
1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3
3 4 2
4 2 1이와 같이 입력이 됐고, 회전 순서가 (3,4,2) -> (4,2,1)이라 해보자
회전 (3,4,2) 수행 경우:
시작은 (1,2) 끝은 (5.6)으로 회전을 다음과 같이 진행하면 다음과 같다.
따라서 회전 결과 다음과 같이 되는 것이다.
이렇게 (4,2,1) 회전까지 수행 한경우 최종 회전한 행렬과 결과는 다음과 같다.
결국 5행에 최소값은 12 이므로 (3,4,2) -> (4,2,1) 순으로 회전한 경우 최소값은 12 인 것이다.
여기서 주의할 점은 이 문제는 입력된 순서대로 회전하는 것이 아니다.
즉 문제에서 (3,4,2) ->(4,2,1) 회전 경우에는 최소가 12,
(4,2,1) ->(3,4,2)로 회전했을 때는 최소가 15 이므로
최종 정답은 12가 되는 것이다.
구현 방향:
이 문제를 구현하기 위해서
회전 하는 경우는 우, 아래, 좌, 위 형태로 탐색하면서 한칸씩 밀며
좌표가 시작점 +1 == 종점 -1 이 같을때 까지 시작 위치 종점위치를 변경하며 회전하면 된다.
모든 경우의 수를 탐색해야 하기 때문에 dfs 백트래킹 방식을 통하여 모든 경우의 수를 탐색하면
정답은 다음과 같다.
정답 코드:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M, K;
static int[][] matrix;
static int r, c, s;
static int[][] origin;
static int[][] cmd; // K개의 (r,c,s) 저장
static boolean[] visited;
static int[] order;
static int answer = Integer.MAX_VALUE;
public static void turn(int r, int c, int s) {
int startX = r - s - 1;
int startY = c - s - 1;
int endX = r + s - 1;
int endY = c + s - 1;
while (true) {
// 더 돌릴 레이어가 없으면 종료
if (startX >= endX || startY >= endY) {
break;
}
//예시 행렬 생성
int[][] temp = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
temp[i][j] = matrix[i][j];
}
}
//우로 이동
for (int i = startY; i < endY; i++) {
temp[startX][i + 1] = matrix[startX][i];
}
//아래로 이동
for (int i = startX; i < endX; i++) {
temp[i + 1][endY] = matrix[i][endY];
}
//좌로 이동
for (int i = endY; i > startY; i--) {
temp[endX][i - 1] = matrix[endX][i];
}
//위로 이동
for (int i = endX; i > startX; i--) {
temp[i - 1][startY] = matrix[i][startY];
}
//결과 저장
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
matrix[i][j] = temp[i][j];
}
}
//안쪽 레이어로 한 칸 들어감
startX += 1;
startY += 1;
endX -= 1;
endY -= 1;
}
}
public static int calMin() {
int min = Integer.MAX_VALUE;
//최종 결과 계산
for (int i = 0; i < N; i++) {
int result = 0;
for (int j = 0; j < M; j++) {
result += matrix[i][j];
}
min = Math.min(min, result);
}
return min;
}
// 연산 순서 전부 조사 (순열)
public static void dfs(int depth) {
if (depth == K) {
// origin -> matrix 복사
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
matrix[i][j] = origin[i][j];
}
}
// 현재 순서대로 회전
for (int idx = 0; idx < K; idx++) {
int opIndex = order[idx];
int rr = cmd[opIndex][0];
int cc = cmd[opIndex][1];
int ss = cmd[opIndex][2];
turn(rr, cc, ss);
}
// 최소값 갱신
int val = calMin();
if (val < answer) answer = val;
return;
}
for (int i = 0; i < K; i++) {
if (!visited[i]) {
visited[i] = true;
order[depth] = i;
dfs(depth + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
//초기 세팅
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
matrix = new int[N][M];
origin = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
int num = Integer.parseInt(st.nextToken());
matrix[i][j] = num;
origin[i][j] = num; //원본도 같이 저장
}
}
// 연산들 저장
cmd = new int[K][3];
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
s = Integer.parseInt(st.nextToken());
cmd[i][0] = r;
cmd[i][1] = c;
cmd[i][2] = s;
}
// 순열 돌리기
visited = new boolean[K];
order = new int[K];
dfs(0);
//최종 결과 출력
System.out.println(answer);
}
}
마무리하며:
작성자는 처음에 입력한 순서대로 회전이 되는줄 착각하며 문제를 구현해서 틀렸었다.
틀렸던 답안을 살리면서 dfs 방식을 추가해야 했기에 시간이 더 오래 걸렸던 것 같다.
앞으로 문제를 더 신중하게 읽으며 정확한 방법일 경우에 구현을 시작해야 겠다고 생각했다.
감사합니다
'코딩 테스트' 카테고리의 다른 글
| [백준] 1911 흙길 보수하기 (JAVA) (0) | 2025.11.23 |
|---|---|
| [백준] 톱니바퀴 (2) (JAVA) (0) | 2025.11.20 |
| [백준] 3190 뱀 (JAVA) (0) | 2025.10.30 |
| [백준] 12100 2048 Easy (JAVA) (0) | 2025.10.28 |
| [백준] 14889 스타트와 링크 (JAVA) (0) | 2025.10.24 |