본문 바로가기
PS/백준

[BOJ 16945번] 매직 스퀘어로 변경하기

by 방준이 2023. 1. 29.
반응형

 

[BOJ 16945번]  매직 스퀘어로 변경하기

 

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

 

16945번: 매직 스퀘어로 변경하기

1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다. 크기가 3×3인 배열 A가 주어졌을 때,

www.acmicpc.net


위의 문제는 3x3 배열 매직 스퀘어의 각 행의 합, 각 열의 합, 대각선의 합이 15라는 사실을 알고 풀어야 하는 문제입니다. 문제에 연결된 매직 스퀘어의 링크(위키백과) 설명을 제대로 읽지 못해 조건을 잘못 걸어 여러 번의 제출에도 해결하지 못하여 쓸데없는 시간을 소요하였습니다.

 

 

내가 생각한 풀이 - 1

우선 문제에 주어진 배열을 살펴보면 아래와 같습니다.

 

 

 위의 3 x 3 배열에서 9개의 수(1 ~ 9)를 채울 수 있는 방법의 수는 어떻게 계산할 수 있을까? 각각의 수는 한 번씩만 등장할 수 있으며, 수를 넣을 수 있는 칸은 9개이다.  9개의 원소를 순서와 상관있게 나열하는 방법의 수는 9! = 362880 이다. 

 

 

첫 번째로 5가 있는 자리에서 출발할 수 있다. 위의 숫자에서는 1~9까지 어떤 숫자든 대입할 수 있다. 임의의 숫자로 바뀌게 될 경우 해당 숫자로 비용을 계산하여 다음 칸으로 이동할 수 있다. 정답에 맞게 5가 위치해 있는 칸에 8을 넣고 다음 숫자로 넘어가면 아래와 같다. 이때 비용은 |5 - 8| = 3 이다. 이와 같이 계산하고 이 정보를 다음 처리에서 사용하면 된다.

 

 

 첫 번째 칸에서 8이라는 숫자를 선택했다. 그럼 2번째 칸에서는 8을 제외한 8가지의 수를 선택 할 수 있다. 마찬가지로 3이라는 숫자를 선택했다. 이때 비용은 |3-3| = 0 이다.

 

 

 이번에도 마찬가지로 4가 위치해 있는 칸에서는 8과 3을 제외한 7가지의 수를 선택할 수 있다. 위와 같은 방식으로 진행을 하면 마지막 칸에서는 1가지의 방법밖에 선택할 수 없을 것이다. 즉 모든 칸에 9가지의 숫자를 나열할 수 있는 방법이 수는 9!로 이는 DFS를 이용한 풀이로 가능하다. 

 

 

풀이 방법 정리

1. DFS 를 이용하여 3 x 3 배열에 모든 숫자(1~9)를 중복되지 않게 나열해 본다.

2. 나열하고 나서 해당 배열이 매직 스퀘어인지 검증한다.

3. 매직 스퀘어인 경우 최솟값을 갱신하여 정답을 구한다.

 

 

구현 - 1

 

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
import java.util.Scanner;
 
public class p16945 {
 
    final static int N = 3;
    static int ans = 1000;
    static boolean[] checked = new boolean[10];
    static int[][] arr = new int[N][N];
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
 
        dfs(00);
        System.out.println(ans);
    }
    private static void dfs(int depth, int cost) {
 
        if(depth == 9 && isMagicSquare()) {
            ans = Math.min(ans, cost);
            return;
        }
 
        int x = depth / 3;
        int y = depth % 3;
 
        for(int num = 1; num <= 9; num++) {
            if(!checked[num]) {
                int temp = arr[x][y];
                checked[num] = true;
                arr[x][y] = num;
                dfs(depth + 1, cost + Math.abs(temp - num));
                checked[num] = false;
                arr[x][y] = temp;
            }
        }
    }
    private static boolean isMagicSquare() {
 
        int rowSum0 = arr[0][0+ arr[0][1+ arr[0][2];
        int rowSum1 = arr[1][0+ arr[1][1+ arr[1][2];
        int rowSum2 = arr[2][0+ arr[2][1+ arr[2][2];
 
        int colSum0 = arr[0][0+ arr[1][0+ arr[2][0];
        int colSum1 = arr[0][1+ arr[1][1+ arr[2][1];
        int colSum2 = arr[0][2+ arr[1][2+ arr[2][2];
 
        int diagonalSum0 = arr[0][0+ arr[1][1+ arr[2][2];
        int diagonalSum1 = arr[2][0+ arr[1][1+ arr[0][2];
 
        if(rowSum0 != 15 || rowSum1 != 15 || rowSum2 != 15return false;
        if(colSum0 != 15 || colSum1 != 15 || colSum2 != 15return false;
        if(diagonalSum0 != 15 || diagonalSum1 != 15return false;
 
        return true;
    }
}
 
cs

 

 

 

 

 

 

 

 

 

 

 

반응형

'PS > 백준' 카테고리의 다른 글

[BOJ 2447번] 별 찍기 - 10  (0) 2021.10.12
[BOJ 1011번] Fly me to the Alpha Centauri  (0) 2021.09.16