[백준] 16945번 매직 스퀘어로 변경하기 - Python / 알고리즘 중급 2/3 - 브루트 포스 - 문제 (연습)

---

---

---

💡 문제

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

크기가 3×3인 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하려고 한다. 한 칸에 있는 수 a를 b로 변경하는 비용은 |a - b| 이다. 예를 들어, 아래와 같은 경우를 살펴보자.

5 3 4
1 5 8
6 4 2

이 배열의 수를 아래와 같이 변경하면 매직 스퀘어가 되고, 비용은 |5 - 8| + |8 - 9| + |4 - 7| = 7 이다.

8 3 4
1 5 9
6 7 2

3×3 크기의 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하는 비용의 최솟값을 구해보자. 배열 A는 1부터 9까지의 수로만 채워져 있고, 매직 스퀘어로 변경한 배열도 1부터 9까지의 수로만 채워져 있어야 한다.

입력

총 세 개의 줄에 걸쳐서 배열 A의 원소가 주어진다.

출력

첫째 줄에 배열 A를 매직 스퀘어로 변경하는 비용의 최솟값을 출력한다.

---

💭 접근

이 문제는 배열의 총 원소가 9개밖에 되지 않으므로 입력받은 배열을 1차원으로 풀고,

1부터 9까지 숫자로 조합 을 만들어 매직 스퀘어가 되는 조건에 맞는 배열을 찾은 뒤,

원본 배열과 각 자리의 숫자의 차를 구해 이 값이 최소가 되는 값을 출력하면 되는 문제이다.

---

📒 코드

def dfs(depth):
    if depth == 9:
        check()
        return

    for i in range(1, 10):
        if i not in tmp:
            tmp.append(i)
            dfs(depth + 1)
            tmp.pop()

def check():
    global ans

    if tmp[0] + tmp[1] + tmp[2] == 15 and \
    tmp[3] + tmp[4] + tmp[5] == 15 and \
    tmp[6] + tmp[7] + tmp[8] == 15 and \
    tmp[0] + tmp[3] + tmp[6] == 15 and \
    tmp[1] + tmp[4] + tmp[7] == 15 and \
    tmp[2] + tmp[5] + tmp[8] == 15 and \
    tmp[0] + tmp[4] + tmp[8] == 15 and \
    tmp[2] + tmp[4] + tmp[6] == 15:
        tmp_ans = 0
        for i in range(9):
            tmp_ans += abs(tmp[i] - graph_1d[i])
        ans = min(ans, tmp_ans)

graph = [list(map(int, input().split())) for _ in range(3)]
graph_1d = []
for i in range(3):
    for j in range(3):
        graph_1d.append(graph[i][j])

ans = 72
tmp = []
dfs(0)

print(ans)

---

💭 후기

2차원 배열을 1차원으로 풀어서 해결하는 참신한 문제였다.

---

🔗 문제 출처

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

---