[알고리즘] 1-9 사이의 중복되지 않은 주어진 입력 9개의 와 3 x 3 마방진 중 최소 변경값 ( Forming a Magic Square)
문제
한글로 쉽게 정리
3 x 3 메트릭스의 입력을 받아 3 x 3 마방진 값 목록과 비교하여 각 마방진과 비교 후에 각 값의 절대값 차이가 제일 작은 값을 구하여라.
원문
We define a magic square to be an n X n matrix of distinct positive integers from 1 to n2 where the sum of any row, column, or diagonal of length n is always equal to the same number: the magic constant.
You will be given a 3 X 3 matrix s of integers in the inclusive range [1,9]. We can convert any digit a to any other digit b in the range [1,9] at cost of |a - b|. Given s, convert it into a magic square at minimal cost. Print this cost on a new line.
Note: The resulting magic square must contain distinct integers in the inclusive range [1,9].
For example, we start with the following matrix s:
1 5 3 4
2 1 5 8
3 6 4 2We can convert it to the following magic square:
1 8 3 4
2 1 5 9
3 6 7 2This took three replacements at a cost of |5 - 8| + |8 - 9| + |4 - 7| = 7.
Function Description
Complete the formingMagicSquare function in the editor below. It should return an integer that represents the minimal total cost of converting the input square to a magic square.
formingMagicSquare has the following parameter(s):
s: a 3 X 3 array of integers
Input Format
Each of the lines contains three space-separated integers of row s[i].
Constraints
Output Format
Print an integer denoting the minimum cost of turning matrix s into a magic square.
Sample Input 0
1 4 9 2
2 3 5 7
3 8 1 5Sample Output 0
1 1Explanation 0
If we change the bottom right value, s[2][2], from 5 to 6 at a cost of |6 - 5| = 1, s becomes a magic square at the minimum possible cost.
Sample Input 1
1 4 8 2
2 4 5 7
3 6 1 6Sample Output 1
1 4Explanation 1
Using 0-based indexing, if we make
s[0][1]->9 at a cost of |9 - 8| = 1
s[1][0]->3 at a cost of |3 - 4| = 1
s[2][0]->8 at a cost of |8 - 6| = 2,
then the total cost will be 1 + 1 + 2 = 4.
해결책
시작
처음에 이 문제를 시작할때 마방진이라는 개념 자체에 어려움이 있었다.(졸업한지가 꽤 되어서 기억조차..) 마방진이 무엇인지 먼저 학습을 하기 위해서 다음의 유튜브 영상을 확인 한 후 마방진 자체에 대한 이해를 시도
마방진
정의
마방진 또는 방진은 n²개의 수를 가로, 세로, 대각선 방향의 수를 더하면 모두 같은 값이 나오도록 n × n 행렬에 배열한 것이다. 마법진 중 하나이다. 일반적인 마방진의 각 칸에는 1부터 n²까지의 수가 한 개씩 들어간다. 마방진은 n이 2일 때를 제외하고 항상 존재한다. (위키백과)
3*3 마방진의 경우
- 1 - 9까지의 수가 나열되며 모든 수의 합은 45가 된다.
- 가로의 합, 세로의 합, 대각선의 합은 15가 되어야 한다. (가로열의 합만 확인해도 15 + 15 + 15 = 45, 이렇게 볼수 있다.)
- 15를 만들기 위해서 3*3마방진이므로 3개의 숫자로 15를 조합하기로 시도
1 5 9
1 6 8
2 6 7
2 8 5
2 9 4
3 8 4
3 7 5
4 5 62번 참조 : 1, 3, 7, 9
3번 참조 : 2, 4, 6, 8
4번 참조 : 5- 위와 같은 분석에 마방진을 한번 일치되어야 하는 라인들을 선으로 그어보니 다음과 같다. 2번 참조된 녀석들은 2로 맞게 들어가면 되고 3번 참조 된 녀석들은 3으로 맞게 들어가면 된다. 다만 한 끝이 1이라면 다른쪽은 9가 되는 식으로 해야 균형이 맞게 잘들어간다.
마방진을 알았으니 이제 풀어야지?
마방진에 대한 비밀을 알았는데 이 원리를 알면 해결이 될 것인가 고민을 했는데 1시간을 고민해도 해결이 안나왔다가 이런 생각이 들었다. 가운데가 5로 고정된 1-9사이의 정수의 조합을 구해서 가로/세로/대각선의 합이 15인 케이스를 구한뒤 입력 값만 구하면 되지 않을까? 라는 생각이 들며 그럼 어떻게 "가운데가 5로 고정된 1-9사이의 정수의 조합"을 구해 볼까 고민을 하게 되었고 DFS를 이용한 구하는 것이 맞다고 생각했다. 그래서 문제를 다음과 같이 풀었다.
풀이
- 가운데가 5로 고정된 1-9사이의 정수의 조합을 구한다.(DFS이용 - 사실 해당 내용은 직접 계산해 하드코딩 해도 되지만 직접 구하고 싶었다. 파이썬의 경우 "itertools.permutations(range(1,10))" 이 코드로 요 내용이 한방에 해결이 되어서 알고리즘은 역시 파이썬이구나 싶긴 하다.)
- 1의 결과 중에 합이 15인 것만 남긴다.
- 입력값으로 구한 메트릭스와 마방진 메트릭스 후보와 비교해서 값을 구한다.
solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
public final static int standard = 15;
/*
* 쓰이지 않음
*/
public static int[][] inputListToArray(List<List<Integer>> s) {
int array[][] = new int[3][3];
for( int i = 0; i < 3 ; i++ ) {
for( int j = 0; j < 3 ; j++ ) {
array[i][j] = s.get(i).get(j);
}
}
return array;
}
/**
* 가운데가 5로 고정된 1-9사이의 정수의 조합을 구한다.(DFS이용)
*/
public static List<List<Integer>> generateToMagicSquare(
List<List<Integer>> candidates,
int[] target,
int pivot
) {
if(pivot == target.length) {
List<Integer> temp = new ArrayList<>();
for( int i = 0; i < target.length ; i++ ) {
temp.add(target[i]);
}
temp.add(4, 5);
candidates.add(temp);
} else {
for( int i = pivot ; i < target.length ; i++ ) {
swap(target, i, pivot);
generateToMagicSquare(candidates, target, pivot + 1);
swap(target, pivot, i);
}
}
return candidates;
}
public static void swap(int array[], int before, int after) {
int temp = array[before];
array[before] = array[after];
array[after] = temp;
}
/**
* 2. 1의 결과 중에 합이 15인 것만 남긴다.
*/
public static List<List<Integer>> filteredMagicSquare(
List<List<Integer>> input) {
return input.stream()
.filter(it -> standard == (it.get(0) + it.get(1) + it.get(2)))
.filter(it -> standard == (it.get(3) + it.get(4) + it.get(5)))
.filter(it -> standard == (it.get(6) + it.get(7) + it.get(8)))
.filter(it -> standard == (it.get(0) + it.get(3) + it.get(6)))
.filter(it -> standard == (it.get(1) + it.get(4) + it.get(7)))
.filter(it -> standard == (it.get(2) + it.get(5) + it.get(8)))
.filter(it -> standard == (it.get(0) + it.get(4) + it.get(8)))
.filter(it -> standard == (it.get(2) + it.get(4) + it.get(6)))
.collect(Collectors.toList());
}
public static int formingMagicSquare(List<List<Integer>> s) {
List<List<Integer>> candidates = new ArrayList<>();
int[] target = {1, 2, 3, 4, 6, 7, 8, 9};
List<List<Integer>> magicSquareCandidates = generateToMagicSquare(
candidates,
target,
0
);
magicSquareCandidates = filteredMagicSquare(magicSquareCandidates);
// 3. 입력값으로 구한 메트릭스와 마방진 메트릭스 후보와 비교해서 값을 구한다.
int answer = Integer.MAX_VALUE;
for(List<Integer> item : magicSquareCandidates) {
int sum = 0;
for( int i = 0 ; i < 3 ; i++ ) {
for( int j = 0 ; j < 3 ; j++ ) {
sum += Math.abs(s.get(i).get(j) - item.get((i * 3) + j));
}
}
if(answer > sum) {
answer = sum;
}
}
return answer;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
List<List<Integer>> s = new ArrayList<>();
IntStream.range(0, 3).forEach(i -> {
try {
s.add(
Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList())
);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
int result = Result.formingMagicSquare(s);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}참조
