김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)

문제 링크 문제 링크

두 문제가 입출력, 제한 등 모든 면에서 완벽하게 같은 문제다.
따라서 같이 서술한다.
3*3 작은 마방진을 채우는 문제.
그냥 경우의 수를 생각해서 쉽게 풀 수 있다.
일단, 빈 칸이 최대 3개인 경우 마방진의 합을 알 수 없는 경우는 오직 빈칸 3개가 대각선으로 위치하는 두 가지 경우밖에 없다.
그 외의 경우 가로든 세로든 대각선이든 최소한 하나의 줄이 빈칸 없이 완성되므로 마방진의 합을 알 수 있게 된다.
마방진의 합을 아는 경우 문제는 매우 쉽다.
그냥 빈칸이 하나인 줄을 찾은 다음에, 그 줄의 빈칸을 채우면 되기 때문이다.
어차피 빈칸이 최대 3개이기 때문에, 언제든 적어도 하나의 줄이 하나의 빈칸만을 가진다.
마방진의 합을 모르는 경우, 간단한 방정식을 풀 필요가 있다.
이때, 대각선의 합과 1행의 합이 같다는 점을 이용할 것이다.
세 빈칸의 값을 각각 \(a\), \(b\), \(c\)라고 하자.
그리고 2, 3행의 빈칸이 아니면서 1행의 빈칸과 같은 열이 아닌 칸의 값을 각각 \(m\), \(n\)이라고 하자.
그렇다면 \(a + b + c = a + (a + b + c - b - m) + (a + b + c - c - n)\)이라 할 수 있다.
이 식을 정리하면 \(a = \frac {(m + n)} {2}\)임을 알 수 있다.
이제 빈칸 하나의 값을 알았으므로 빈칸이 2개인, 마방진의 합을 아는 문제가 되니 풀 수 있게 된다.

#!python

# n번째 빈칸에 val을 채우는 함수
def solve(n, val):
    # 빈칸의 좌표를 가져온다
    i, j = blanks[0][n], blanks[1][n]
    # 보드에 값을 채우고 합을 저장하고 있는 sums 리스트를 갱신한다
    board[i][j] = val
    sums[0][i] += val
    sums[1][j] += val
    # 채워진 빈칸을 blanks에서 삭제한다
    del blanks[0][n]
    del blanks[1][n]

# board: 마방진
# sums[0][i]: i번째 행의 합
# sums[1][i]: i번째 열의 합
# blanks[0][i]: i번째 빈칸의 행 좌표
# blanks[1][i]: i번째 빈칸의 열 좌표
board = [list(map(int, input().split())) for _ in range(3)]
sums = [[0 for _ in range(3)] for _ in range(2)]
blanks = [[], []]

# 마방진을 순회하면서 sums와 blanks 리스트를 채운다
for i, line in enumerate(board):
    for j, e in enumerate(line):
        sums[0][i] += e
        sums[1][j] += e
        if not e:
            blanks[0].append(i)
            blanks[1].append(j)

# 빈칸이 대각선으로 3개 있는 경우
# 이 경우 바로 합을 알 수 없으므로 방정식을 통해 알아내야 한다
# 각 빈칸을 a, b, c라고 하고 2행, 3행의 빈칸이 아니면서 1행의 빈칸과 같은 열이 아닌 칸을 각각 m, n이라고 할 때
# 대각선의 합과 1행의 합은 같아야 하므로 a + b + c = a + (a + c - m) + (a + b - n)
# 0 = a - n + a - m
# 0 = 2a - m - n
# a = (m + n) // 2
if blanks in ([[0, 1, 2], [0, 1, 2]], [[0, 1, 2], [2, 1, 0]]):
    # 상술한 방정식으로 a, 즉 첫 번째 빈칸의 값을 구한다
    # 빈칸 하나를 구했으므로 합도 계산할 수 있다
    add = (board[2][1] + board[1][blanks[1][2]]) // 2
    ans = sums[0][0] + add
    
    # q는 남은 빈칸 개수
    q = 2

    # 0번째 빈칸에 구한 값을 채워넣는다
    solve(0, add)
# 그 외의 경우 항상 적어도 하나의 줄을 통해 전체 합을 구할 수 있다
# 범위가 자연수이므로 마방진에서 합이 가장 큰 줄이 무조건 그 마방진의 합이 된다
else:
    # sum[0]은 행, sum[1]은 열, 그 뒤의 리스트가 대각선
    ans = max(sums[0] + sums[1] + [board[0][0] + board[1][1] + board[2][2], board[0][2] + board[1][1] + board[2][0]])

    # q는 남은 빈칸 개수
    q = len(blanks[0])

# 남은 빈칸을 전부 채울 때까지 반복
while q:
    # 각 빈칸에 대해
    for i in range(q):
        # 남은 빈칸이 하나인 줄부터 해결
        if 1 not in (blanks[0].count(blanks[0][i]), blanks[1].count(blanks[1][i])):
            continue
        # 행의 빈칸이 자신 혼자인 경우
        if blanks[0].count(blanks[0][i]) == 1:
            t = 0
        # 열의 빈칸이 자신 혼자인 경우
        else:
            t = 1
        # 해당 빈칸에 전체 합에서 그 빈칸이 속한 행/열의 합을 뺀 값을 채워넣는다
        solve(i, ans - sums[t][blanks[t][i]])
        q -= 1
        break

for i in range(3):
    print(*board[i])

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑