[백준] 16945 매직 스퀘어로 변경하기 - Backtracking / Java

• 문제 링크

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

 

• 풀이 과정

3 * 3 배열에 각 좌표의 정수 값을 입력받고, 각각의 정수를 사용했는지 확인할 boolean 형 배열을 생성한다.

 

백트래킹을 통해 최상단 행에서부터 가로로 값을 변환하는 모든 경우의 수를 구하며,

변환 비용을 sum 에 누적(sum + Math.abs(tmp - i)) 시킨다.

 

해당 행 완료(x == 3) 시 아래 행으로 넘어가는 방식(recur(y + 1, 0, sum)) 으로

사각형을 채울 수 있는 모든 경우의 수를 구한다.

 

만약 해당 경우의 수에서 두 대각선의 합이 같다면, (map[0][0] + map[2][2] == map[2][0] + map[0][2])

isEqual 함수에서 해당 값과 현재 사각형의 가로, 세로 값과 비교하여

모두 일치 시 true, 하나라도 불일치 시 false 를 반환한다.

 

만약 문제에 조건에 부합하는 사각형이 구해졌을 시, 해당 사각형을 만드는데 소요된 비용(sum) 과 최소값을 비교하여

최종적으로 갱신된 최소값을 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    static int[][] map;
    static boolean[] visit;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        map = new int[3][3];
        visit = new boolean[10];

        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }

        recur(0, 0, 0);

        bw.write(min + "\n");
        bw.flush();
    }

    private static void recur(int y, int x, int sum) {
        if (x == 3) {
            recur(y + 1, 0, sum);
            return;
        }

        if (y == 3) {
            int diag = map[0][0] + map[2][2];

            if (diag == map[2][0] + map[0][2]) {
                if (isEqual(diag + map[1][1]))
                    min = Math.min(min, sum);
            }
            return;
        }

        int tmp = map[y][x];
        for (int i = 1; i <= 9; i++) {
            if (!visit[i]) {
                visit[i] = true;
                map[y][x] = i;
                recur(y, x + 1, sum + Math.abs(tmp - i));
                visit[i] = false;
                map[y][x] = tmp;
            }
        }
    }

    private static boolean isEqual(int diag) {
        for (int i = 0; i < 3; i++) {
            int vert = 0;
            int horiz = 0;
            for (int j = 0; j < 3; j++) {
                vert += map[i][j];
                horiz += map[j][i];
            }

            if (vert != diag || horiz != diag)
                return false;
        }

        return true;
    }

}