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

문제

 

 

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

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

---

풀이

크기가 3 × 3인 배열을 1부터 9까지의 수가 1개씩 들어있고 모든 행, 열, 대각선의 합이 모두 같은 매직 스퀘어로 변경하려고 합니다. 한 칸에 있는 수 a를 b로 변경하는 비용은 |a - b|일 때 매직 스퀘어로 변경하는 최소 비용을 구해야 합니다.

---

코드

C언어

지난번에 작성했던 스도쿠 문제와 비슷합니다. 배열의 크기는 3 x 3으로 크지 않기 때문에 모든 칸을 살펴볼 수 있습니다.

2차원 정수 배열 arr로 3 x 3 크기의 보드를 표현하고 visited로 해당 숫자 사용 여부를 표현합니다. dfs 함수에서 보드의 (x, y)의 위치에 있는 숫자를 arr[y][x]라고 할 때 dpth는 y를, idx는 x를 의미합니다. sum은 dfs 함수를 실행하면서 매직스퀘어를 만들기 위한 비용의 합을 의미합니다. 메인 함수에서 모든 입력을 받은 후에 xy 좌표 (0,0)부터 시작한다는 의미로 dfs(0, 0, 0)을 실행합니다.

정수 tmp를 arr[dpth][idx]값으로 초기화한 뒤에 i를 포함한 for문을 이용하여 어떤 수 i를 사용하지 않았다면 arr[dpth][idx]값을 i로 지정합니다. i를 사용했다는 의미로 visited[i]를 1로 변경하고 해당 수로 변경한 비용만큼 sum에 더하고 dfs를 재귀적으로 실행합니다.

다른 수도 확인해봐야 하기 때문에 arr[dpth][idx]를 바꾸기 전의 값인 tmp로 변경하고 다른 칸에서 i를 사용할 수도  있으니 visited[i]를 0으로 초기화합니다.

idx가 3이 됐다면 해당 y 좌표의 모든 x값을 확인한 것이므로 dfs(dpth + 1, 0, sum)을 통해 다음 y 좌표의 처음, 즉 (0, y + 1)부터 지금까지의 비용을 유지한 채로 시작합니다. dpth가 3이 됐다면 모든 칸을 다 채웠다는 것이므로 매직스퀘어가 완성됐는지 확인합니다.

왼쪽 상단 오른쪽 하단 대각선의 합을 의미하는 diagonal이 오른쪽 상단 왼쪽 하단 대각선의 합과 같다면 square 함수의 매개변수로 diagonal이 들어가게 되고 i와 j를 포함하는 이중 for문을 이용하여 각 행의 합과 열의 합을 의미하는 horizontal과 vertical이 diagonal과 같지 않다면 0(False)을 반환합니다. 모든 비교가 끝나면 모두 같다는 것을 의미하므로 1(True)을 반환합니다.

square 함수에서 1(True)을 반환받았다면 최소비용을 의미하는 min과 비교하여 더 작은 값을 구합니다.

모든 칸을 확인하면 메인함수에서 min의 값을 출력합니다.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#define math_min(a, b) a < b ? a : b
int arr[3][3], visited[10], min = INT_MAX;
int square(int diagonal) {
	for (int i = 0; i < 3; i++) {
		int horizontal = 0, vertical = 0;
		for (int j = 0; j < 3; j++) {
			horizontal += arr[i][j];
			vertical += arr[j][i];
		}
		if (horizontal != diagonal || vertical != diagonal) return 0;
	}
	return 1;
}
void dfs(int dpth, int idx, int sum) {
	if (idx == 3) {
		dfs(dpth + 1, 0, sum);
		return;
	}
	if (dpth == 3) {
		int diagonal = 0;
		for (int i = 0; i < 3; i++) {
			diagonal += arr[i][i];
		}
		if (diagonal == arr[2][0] + arr[1][1] + arr[0][2]) {
			if (square(diagonal)) {
				min = math_min(min, sum);
			}
		}
		return;
	}
	int tmp = arr[dpth][idx];
	for (int i = 1; i <= 9; i++) {
		if (!visited[i]) {
			visited[i] = 1;
			arr[dpth][idx] = i;
			dfs(dpth, idx + 1, sum + abs(tmp - i));
			arr[dpth][idx] = tmp;
			visited[i] = 0;
		}
	}
}
main() {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	dfs(0, 0, 0);
	printf("%d", min);
}

자바

위의 C언어를 이용한 풀이와 동일한 방법을 사용하였습니다.

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

public class Main {

    static int min = Integer.MAX_VALUE;
    static boolean[] visited;
    static int[][] arr;

    public static boolean square(int diagonal) {
        for (int i = 0; i < 3; i++) {
            int horizontal = 0, vertical = 0;
            for (int j = 0; j < 3; j++) {
                horizontal += arr[i][j];
                vertical += arr[j][i];
            }
            if (horizontal != diagonal || vertical != diagonal) return false;
        }
        return true;
    }

    public static void dfs(int dpth, int idx, int sum) {
        if (idx == 3) {
            dfs(dpth + 1, 0, sum);
            return;
        }
        if (dpth == 3) {
            int diagonal = arr[0][0] + arr[1][1] + arr[2][2];
            if (diagonal == arr[2][0] + arr[1][1] + arr[0][2]) {
                if (square(diagonal)) {
                    min = Math.min(min, sum);
                }
            }
            return;
        }
        int tmp = arr[dpth][idx];
        for (int i = 1; i <= 9; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[dpth][idx] = i;
                dfs(dpth, idx + 1, sum + Math.abs(tmp - i));
                arr[dpth][idx] = tmp;
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        visited = new boolean[10];
        arr = new int[3][3];
        for (int i = 0; i < 3; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0, 0, 0);
        System.out.println(min);
    }
}

 

---

결론

처음에 문제를 풀 때 visited 배열을 사용하지 않아서 테스트 케이스 1개를 돌리는 데에도 제한 시간인 2초를 훌쩍 뛰어넘는 시간이 걸렸습니다. 문제 조건을 다시 읽어보니 그제야 N x N 크기의 배열에 1부터 N^2까지의 수가 1개씩 있다는 조건을 알게 되었습니다. 다음에 다른 문제를 풀 때에도 이렇게 문제 조건을 놓치는 경우가 없도록 노력해야겠습니다.