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

www.acmicpc.net/problem/16945

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

처음 봤을 땐 무슨 문젠가 싶지만 3 * 3 칸만 채우면 되므로 브루트포스 - 백트래킹을 사용하면 된다.

 

사각형을 모든 경우의 수로 채우는 백트래킹을 사용한다. cnt는 3 * 3칸 내에서 칸의 위치를 의미한다. 스퀘어를 1~9로 채우고 난 후 매직스퀘어 조건에 충족한다면 -> 원래 스퀘어와의 차이를 계산 -> 최솟값을 리턴

 

매직 스퀘어 조건은 가로 세로 대각선의 합이 모두 같은 것이다. 이 때 합은 15여야 한다. 왜냐면 1~9까지 합이 45이기 때문에 3등분하면 15이기 때문. 따라서 isValid 함수를 만들어서 매직 스퀘어에 해당하는지 확인한다.

 

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <limits.h>

using namespace std;

int square[3][3], sq2[3][3];
int visited[10];
int result = INT_MAX;

bool isValid()
{
  int sum = 0, sum2 = 0;

  //row 합 col 합
  for (int i = 0; i < 3; i++)
  {
    sum = sq2[i][0] + sq2[i][1] + sq2[i][2];
    sum2 = sq2[0][i] + sq2[1][i] + sq2[2][i];
    if (sum != 15 || sum2 != 15)
    {
      return false;
    }
  }

  //대각선 합
  if (sq2[0][0] + sq2[1][1] + sq2[2][2] != 15)
  {
    return false;
  }

  if (sq2[0][2] + sq2[1][1] + sq2[2][0] != 15)
  {
    return false;
  }

  return true;
}

int calculate()
{
  int sum = 0;
  for (int i = 0; i < 3; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      sum += abs(square[i][j] - sq2[i][j]);
    }
  }
  return sum;
}

void BackTracking(int cnt)
{
  if (cnt == 9)
  {
    if (isValid())
    {
      result = min(result, calculate());
    }
    return;
  }

  int row = cnt / 3, col = cnt % 3;
  for (int i = 1; i < 10; i++)
  {
    if (visited[i])
      continue;

    sq2[row][col] = i;
    visited[i] = 1;
    BackTracking(cnt + 1);
    visited[i] = 0;
  }
}

int main(void)
{

  for (int i = 0; i < 3; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      scanf("%d", &square[i][j]);
    }
  }

  BackTracking(0);

  printf("%d\n", result);

  return 0;
}