[백준/JAVA] 16945번: 매직 스퀘어로 변경하기

📖 문제

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

 

 

 

💡  풀이 방식

• 백트래킹

1. 3x3 배열에 모든 숫자 1-9를 중복되지 않게 나열한다.

2. 나열 후, 해당 배열이 매직 스퀘어( = 가로,세로, /, \의 합이 모두15인지) 확인한다.

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

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[][] A;
    static boolean[] chk = new boolean[10]; // 1-9 숫자 사용 여부
    static int answer = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        A = new int[3][3];
        for(int i = 0 ; i < 3 ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < 3 ; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        dfs(0,0);
        System.out.println(answer);
    }
    
    private static void dfs(int depth, int sum) {
        if(depth == 9 && isMagicSquare()) {
            answer = Math.min(answer, sum);
            return;
        }
        
        int x = depth/3;
        int y = depth%3;
        
        for(int i = 1 ; i <= 9 ; i++) {
            if(!chk[i]) {
                int tmp = A[x][y];
                
                // 숫자 i 사용해서 현재 칸 (x,y) 채우기
                chk[i] = true;
                A[x][y] = i;
                
                dfs(depth + 1, sum + Math.abs(tmp - i));    // 비용 갱신하며 다음 칸으로 이동
                
                // 원상복구
                chk[i] = false;
                A[x][y] = tmp;
            }
        }
    }
    
    // 가로,세로, \, /의 합이 모두 15인지 확인하는 메소드
    private static boolean isMagicSquare() {
        int rSum0 = A[0][0] + A[0][1] + A[0][2];
        int rSum1 = A[1][0] + A[1][1] + A[1][2];
        int rSum2 = A[2][0] + A[2][1] + A[2][2];
        
        int cSum0 = A[0][0] + A[1][0] + A[2][0];
        int cSum1 = A[0][1] + A[1][1] + A[2][1];
        int cSum2 = A[0][2] + A[1][2] + A[2][2];
        
        int dSum0 = A[0][0] + A[1][1] + A[2][2];
        int dSum1 = A[0][2] + A[1][1] + A[2][0];
        
        if(rSum0 != 15 || rSum1 != 15 || rSum2 != 15)   return false;
        if(cSum0 != 15 || cSum1 != 15 || cSum2 != 15)   return false;
        if(dSum0 != 15 || dSum1 != 15)   return false;
        
        return true;
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

숫자 뽑을 때 배열 말고 리스트를 쓰셨다. 조금 다르다.

개인적으로는 이 풀이가 더 이해하기 쉬웠다. ✅

import java.io.*;
import java.util.*;
 
public class Main {
    static boolean[] mark = new boolean[10];
    static int[] arr = {1,2,3,4,5,6,7,8,9};
 
    static ArrayList<Integer> v = new ArrayList<>();
    static ArrayList<Integer> nums = new ArrayList<>();
 
    static int answer = 999999;
 
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
 
        for(int i = 0; i < 9; i++) {
            int n = Integer.parseInt(sc.next());
            nums.add(n);
        }
 
        DFS(0);
        System.out.print(answer);
    }
 
    static void DFS(int depth) {
        if(depth == 9) {
            if(IsItMagicS()) {
                int sum = 0;
                for(int i = 0; i < 9; i++)
                    sum += Math.abs(nums.get(i) - v.get(i));
                answer = Math.min(answer, sum);
            }
            return;
        }
 
        for(int i = 0 ; i < 9 ; i++) {    
            if(mark[i]) continue;
 
            mark[i] = true;
            v.add(arr[i]);
 
            DFS(depth+1);
 
            v.remove(v.size()-1);
            mark[i] = false;
        }
    }
 
    static boolean IsItMagicS() {
        if(v.get(0) + v.get(1) + v.get(2) != 15) return false;
        if(v.get(3) + v.get(4) + v.get(5) != 15) return false;
        if(v.get(6) + v.get(7) + v.get(8) != 15) return false;
 
        if(v.get(0) + v.get(3) + v.get(6) != 15) return false;
        if(v.get(1) + v.get(4) + v.get(7) != 15) return false;
        if(v.get(2) + v.get(5) + v.get(8) != 15) return false;
 
        if(v.get(0) + v.get(4) + v.get(8) != 15) return false;
        if(v.get(2) + v.get(4) + v.get(6) != 15) return false;
 
        return true;
    }
}

 

백준 16945. 매직 스퀘어로 변경하기

---

💦 어려웠던 점

- 백트래킹 사용할 생각을 하지 못 했다,,

- 매직스퀘어 설명을 보지 않아서 틀렸다,,

 

 

🧐 새로 알게 된 내용

- 문제 해결 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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