안녕하세요!
이번 포스팅에서는 오늘 저를 많이 힘들게 한.. 백준의 배열 돌리기 4 문제 풀이를 작성해보겠습니다!
문제
요약
2차원 배열이 주어지고, 회전 연산이 주어집니다.
회전 연산의 (r, c, s) 는 (r-s,c-s) 부터 (r+s,c+s) 까지의 범위를 시계 방향으로 한 칸씩 움직인다는 의미입니다.
회전 연산의 순서에 따라서 배열 행의 합 중 최솟값이 달라집니다.
연산 순서를 바꾸면서 행의 합 최솟값을 찾는 문제입니다.
처음 생각한 방법
이 문제를 풀기 이전에 배열 돌리기 1 문제를 풀었어서 배열을 방향에 맞춰 돌리는 것은 익혔습니다.
그런데 회전 연산이 순서에 따라 달라진다고 해서 순열을 이용해서 풀면 어떨까라는 생각을 했고,
많은 시도 끝에 결국 성공했습니다!
코드 설명
static int d, N, M, K, min, map[][], calc[][];
static boolean isSelect[];
// 시계방향 우 하 좌 상
static int[] dr = {0, 1, 0, -1};
static int[] dc = {1, 0, -1, 0};static 변수들입니다.
메소드를 나눴기 때문에, 입력으로 들어오는 N , M , K , map[][] , calc[][] 는 main 밖에 선언했습니다.
d 는 현재 방향을 나타내는 변수고 min 은 출력할 결과값입니다.
그 아래 dr, dc 배열은 시계방향을 나타내는 배열입니다.
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()); // 연산 갯수
min = Integer.MAX_VALUE; // 리턴할 답
d = 0; // 현재 방향
map = new int[N+2][M+2]; // 입력받을 배열 (+2만큼 설정해 0은 벽)
calc = new int[K][3]; // 연산 배열
isSelect = new boolean[K]; // 연산 선택 여부
// 배열 초기화
for (int i = 1; i <= N; ++i) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 1; j <= M; ++j) {
int num = Integer.parseInt(st.nextToken());
map[i][j] = num;
}
}
// 연산 배열 초기화
for (int i = 0; i < K; ++i) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < 3; ++j) {
calc[i][j] = Integer.parseInt(st.nextToken());
}
}
// 연산 순열 탐색
perm(0, map);
System.out.println(min);
}main 메소드입니다.
입력을 모두 초기화하고, 회전 연산은 r, c, s 세 가지가 들어오기 때문에 이차원 배열의 크기를 [K][3] 으로 초기화했습니다.
입력이 많아서 BufferedReader 와 StringTokenizer 로 입력 처리했습니다.
// 연산 순열
private static void perm(int cnt, int[][] arr) {
if (cnt == K) {
minValue(arr);
return;
}
for (int i = 0; i < K; i++) {
if (!isSelect[i]) {
isSelect[i] = true;
// 매개변수로 넘겨줄 배열을 perm으로 받은 arr에서 복사
int[][] param = new int[N+2][M+2];
for (int j = 1; j <= N; j++) {
System.arraycopy(arr[j], 0, param[j], 0, arr[j].length);
}
perm(cnt+1, rotate(calc[i][0], calc[i][1], calc[i][2], param)); // 회전 수행 후 결과 배열로 재귀
isSelect[i] = false;
}
}
}순열은 cnt==K 라면 최솟값을 찾고 리턴합니다.
cnt==K 가 아니라면 반복문을 순회합니다.
isSelect 가 true 라면 아무런 작업도 하지 않고,
false 라면 방문했다고 체크하고 현재 회전 연산에 맞는 회전을 해줍니다.
재귀호출이 리턴되어 돌아왔다면 isSelect 체크를 다시 false 로 해제하고 반복문을 순회합니다.
이 때, 주의할 점이 있습니다.
배열은 참조 변수이기 때문에 순열을 구할 때마다 초기화 작업을 수행해야 합니다.
그래서 파라미터로 넘기는 배열을 새로 선언해 현재 메소드의 매개변수인 arr 를 param 으로 복사해서 회전 메소드인 rotate 의 매개변수로 전달합니다.
arr 를 그대로 rotate 의 매개변수로 전달한다면 배열은 초기화가 되지 않아 회전된 배열이 계속 누적될 것입니다.
그렇다면, 현재 매개변수로 perm 에 들어온 arr 는 무엇일까요?
바로 직전 순열의 회전 연산을 수행한 arr 일 것입니다.
위의 그림에서 for문에서 (3,4,2) 회전 연산을 선택하고 perm 을 재귀호출했다면, 그 다음 perm 의 arr 는 (3,4,2) 회전 연산을 수행한 후의 배열이 될 것입니다.
그 후 다시 재귀호출로 (4,2,1) 회전 연산을 선택하고 perm 을 재귀호출하면 그 다음 arr 는 (4,2,1) 연산이 수행된 배열일 것입니다.
이 때 cnt==K 를 만족하고 리턴하게되는것입니다.
그러면 현재 메소드의 호출이 만료되고 전의 perm 메소드로 돌아가니까 그 때의 arr 는 (3,4,2) 연산을 수행한 후의 배열이 될 것입니다.
// 배열 회전 메소드
private static int[][] rotate(int r, int c, int s, int[][] arr) {
int sr = r-s;
int sc = c-s;
int er = r+s;
int ec = c+s;
int nr = sr;
int nc = sc;
int cnt = 0;
int[][] rotated = new int[N+2][M+2];
int center = arr[r][c]; // center는 무조건 숫자 하나로, 회전이 끝난 후에 삽입
while(cnt < s) {
int num = arr[nr][nc]; // 현재 위치의 숫자를 받아온다
// rotated가 0이 아니면 이미 채워진 것. 회전할 시작 좌표와 끝 좌표로 위치 유효성 탐색
if (!isValid(sr, sc, er, ec, nr+dr[d], nc+dc[d]) || rotated[nr+dr[d]][nc+dc[d]] != 0) {
if (d == 3) { // 4방향 다 돌았으면 한 바퀴 회전한 것
cnt++;
nr = sr + cnt;
nc = sc + cnt;
d = 0;
continue;
} else {
d++;
}
}
// 방향만큼 좌표를 더해서 rotated 배열에 넣어줌
nr += dr[d];
nc += dc[d];
rotated[nr][nc] = num;
}
rotated[r][c] = center; // 회전 후 center 삽입
// 매개변수로 받은 arr에 회전 결과 복사
for (int i = sr; i <= er; ++i) {
System.arraycopy(rotated[i], sc, arr[i], sc, ec-sc+1);
}
return arr;
}rotate 메소드입니다.
시작 행/열인 sr, sc 와 끝 행/열인 er, ec 를 계산해 변수로 초기화해 경계를 검사합니다.
현재 회전시킬 위치를 가리키는 nr, nc 는 처음에는 시작 위치와 동일하게 설정하고, 회전 횟수인 cnt 변수도 설정합니다.
변수가 회전되면서 값이 덮어지면 안되므로, rotated 변수를 새로 설정해 arr 의 값을 이용해 회전을 진행하고 회전이 끝난 후에 arr 에 회전을 진행한 부분만 복사해 리턴합니다.
while 문을 반복 수행하면서 회전을 진행합니다.
만약 경계를 벗어나고, rotated 배열에 0이 아닌 값이 저장되어있다면 이미 회전이 완료된 위치입니다.
그래서 d 변수를 1 증가시킵니다.
여기서 방향 배열의 인덱스를 뜻하는 d 변수가 3이 되면 한 바퀴 회전을 끝낸 것이므로, 회전 시작 위치를 nr, nc 에 다시 세팅해주고 d 를 0으로 초기화합니다. cnt 를 하나 증가시키고 반복문을 continue 합니다.
continue 문을 지나서 내려왔다면 위치를 방향에 맞춰 변경하고, rotated 에 num 을 저장합니다.
회전은 s 만큼 진행하며, 이렇게 진행하면 가장 센터인 (r,c) 좌표의 값만 남습니다.
이 값을 rotated 에 마저 저장하고 배열을 복사해 리턴합니다.
// 좌표 유효성 체크
private static boolean isValid(int sr, int sc, int er, int ec, int r, int c) {
if (r>=sr && c>=sc && r<=er && c<=ec) return true;
return false;
}경계를 체크하는 isValid 메소드입니다.
// 배열을 순회하면서 최솟값 찾기
private static void minValue(int[][] arr) {
for (int i = 1; i <= N; ++i) {
int sum = 0;
for(int j = 1; j <= M; ++j) {
sum += arr[i][j];
if (sum > min) break;
}
if (sum < min) min = sum;
}
}최솟값은 한 행의 합 기준이므로, static 변수인 min 과 비교해가면서 찾아줍니다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int d, N, M, K, min, map[][], calc[][];
static boolean isSelect[];
// 시계방향 우 하 좌 상
static int[] dr = {0, 1, 0, -1};
static int[] dc = {1, 0, -1, 0};
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()); // 연산 갯수
min = Integer.MAX_VALUE; // 리턴할 답
d = 0; // 현재 방향
map = new int[N+2][M+2]; // 입력받을 배열 (+2만큼 설정해 0은 벽)
calc = new int[K][3]; // 연산 배열
isSelect = new boolean[K]; // 연산 선택 여부
// 배열 초기화
for (int i = 1; i <= N; ++i) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 1; j <= M; ++j) {
int num = Integer.parseInt(st.nextToken());
map[i][j] = num;
}
}
// 연산 배열 초기화
for (int i = 0; i < K; ++i) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < 3; ++j) {
calc[i][j] = Integer.parseInt(st.nextToken());
}
}
// 연산 순열 탐색
perm(0, map);
System.out.println(min);
}
// 연산 순열
private static void perm(int cnt, int[][] arr) {
if (cnt == K) {
minValue(arr);
return;
}
for (int i = 0; i < K; i++) {
if (!isSelect[i]) {
isSelect[i] = true;
// 매개변수로 넘겨줄 배열을 perm으로 받은 arr에서 복사
int[][] param = new int[N+2][M+2];
for (int j = 1; j <= N; j++) {
System.arraycopy(arr[j], 0, param[j], 0, arr[j].length);
}
perm(cnt+1, rotate(calc[i][0], calc[i][1], calc[i][2], param)); // 회전 수행 후 결과 배열로 재귀
isSelect[i] = false;
}
}
}
// 배열 회전 메소드
private static int[][] rotate(int r, int c, int s, int[][] arr) {
int sr = r-s;
int sc = c-s;
int er = r+s;
int ec = c+s;
int nr = sr;
int nc = sc;
int cnt = 0;
int[][] rotated = new int[N+2][M+2];
int center = arr[r][c]; // center는 무조건 숫자 하나로, 회전이 끝난 후에 삽입
while(cnt < s) {
int num = arr[nr][nc]; // 현재 위치의 숫자를 받아온다
// rotated가 0이 아니면 이미 채워진 것. 회전할 시작 좌표와 끝 좌표로 위치 유효성 탐색
if (!isValid(sr, sc, er, ec, nr+dr[d], nc+dc[d]) || rotated[nr+dr[d]][nc+dc[d]] != 0) {
if (d == 3) { // 4방향 다 돌았으면 한 바퀴 회전한 것
cnt++;
nr = sr + cnt;
nc = sc + cnt;
d = 0;
continue;
} else {
d++;
}
}
// 방향만큼 좌표를 더해서 rotated 배열에 넣어줌
nr += dr[d];
nc += dc[d];
rotated[nr][nc] = num;
}
rotated[r][c] = center; // 회전 후 center 삽입
// 매개변수로 받은 arr에 회전 결과 복사
for (int i = sr; i <= er; ++i) {
System.arraycopy(rotated[i], sc, arr[i], sc, ec-sc+1);
}
return arr;
}
// 좌표 유효성 체크
private static boolean isValid(int sr, int sc, int er, int ec, int r, int c) {
if (r>=sr && c>=sc && r<=er && c<=ec) return true;
return false;
}
// 배열을 순회하면서 최솟값 찾기
private static void minValue(int[][] arr) {
for (int i = 1; i <= N; ++i) {
int sum = 0;
for(int j = 1; j <= M; ++j) {
sum += arr[i][j];
if (sum > min) break;
}
if (sum < min) min = sum;
}
}
}마무리
저는 역시 시뮬레이션 문제는 너무 어렵습니다..
아직 배열이 많이 부족한 탓이겠죠..?
앞으로 일주일에 적어도 1~2번은 시뮬레이션 문제를 풀어야겠어요!
이번 포스팅도 읽어주셔서 감사합니다 :)
