백준 숫자 할당 [32825] 파이썬(Python) 코드 + 해설

백준 32825 숫자 할당 문제

 

백준 32825번 문제는 solved.ac기준 골드 4입니다.

python3말고 pypy3로 해야 시간 초과가 안납니다.

 

1. 문제 설명

이 문제는 5×5 크기의 격자판에 숫자를 배치하는 문제입니다. 변수 a부터 m까지 총 13개의 변수에 1부터 13까지의 숫자를 각각 한 번씩 할당해야 하며, 주어진 8개의 방정식을 만족해야 합니다.

방정식은 다음과 같습니다:

1. A=a+e+i+l
2. B=b+f+j+m
3. C=c+g+k
4. D=d+h
5. E=a+b+c+d
6. F=e+f+g+h
7. G=i+j+k
8. H=l+m

여기서 A부터 H까지는 주어진 정수입니다.

2. 문제 해결 방법

2.1 전체적인 전략

• 백트래킹(Backtracking)을 사용하여 모든 가능한 숫자 할당을 탐색합니다.
• 각 단계에서 현재까지의 할당이 방정식을 만족할 수 있는지 가지치기(Pruning)를 통해 확인하여 불필요한 탐색을 줄입니다.
• 할당된 숫자들은 1부터 13까지의 서로 다른 정수입니다.

2.2 구현 세부사항

1. 변수와 방정식 설정
   • 변수 목록: a부터 m까지 총 13개.
   • 각 변수는 1부터 13까지의 숫자 중 하나를 할당받습니다.
   • 변수의 인덱스는 편의를 위해 0부터 12까지로 설정합니다.
2. 백트래킹 함수 작성
   • 현재까지 할당된 변수들과 사용된 숫자 집합을 인자로 받는 재귀 함수를 작성합니다.
   • 변수들을 순서대로 할당합니다.
   • 각 단계에서 가능한 숫자들(아직 사용되지 않은 숫자들)에 대해 반복합니다.
3. 가지치기 조건 설정
   • 각 방정식을 미리 어느 변수들이 포함되어 있는지 매핑합니다.
   • 변수를 할당할 때마다 해당 변수가 포함된 방정식의 현재 합과 필요한 합을 계산합니다.
   • 현재 할당된 값들로부터 방정식을 만족할 가능성이 없으면 해당 경로를 더 이상 탐색하지 않습니다.
   • 예를 들어, 방정식 A=a+e+i+l에서 a만 할당된 상태라면, 나머지 변수들 e, i, l에 할당될 수 있는 최소값과 최대값을 계산하여 A를 만족할 수 있는지 확인합니다.
4. 해결 방법의 효율성
   • 가지치기를 통해 탐색 공간을 크게 줄일 수 있습니다.
   • 백트래킹 알고리즘은 최대 약 13!개의 경우의 수를 가질 수 있지만, 가지치기를 통해 실제 탐색하는 경우의 수는 매우 작아집니다.

3. 백준 32825 숫자 할당 정답 파이썬 코드

import sys

# 입력 받기
A, B, C, D, E, F, G, H = map(int, sys.stdin.readline().split())

# 변수 인덱스 매핑
variables = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm']

# 방정식 매핑
equations = {
    'A': {'vars': [0, 4, 8, 11], 'value': A},
    'B': {'vars': [1, 5, 9, 12], 'value': B},
    'C': {'vars': [2, 6, 10], 'value': C},
    'D': {'vars': [3, 7], 'value': D},
    'E': {'vars': [0, 1, 2, 3], 'value': E},
    'F': {'vars': [4, 5, 6, 7], 'value': F},
    'G': {'vars': [8, 9, 10], 'value': G},
    'H': {'vars': [11, 12], 'value': H}
}

total_solutions = 0

used_numbers = [False] * 14  # 1부터 13까지 사용 여부
assigned_values = [0] * 13   # 각 변수에 할당된 값

def is_possible(eq_name):
    eq = equations[eq_name]
    current_sum = 0
    unassigned_vars = []
    for idx in eq['vars']:
        if assigned_values[idx]:
            current_sum += assigned_values[idx]
        else:
            unassigned_vars.append(idx)
    min_possible = current_sum + len(unassigned_vars) * 1
    max_possible = current_sum + len(unassigned_vars) * 13
    return eq['value'] >= min_possible and eq['value'] <= max_possible

def check_constraints(var_idx):
    # 변수 var_idx가 포함된 모든 방정식을 확인
    var_equations = []
    for eq_name, eq in equations.items():
        if var_idx in eq['vars']:
            var_equations.append(eq_name)
    for eq_name in var_equations:
        if not is_possible(eq_name):
            return False
    return True

def backtrack(idx):
    global total_solutions
    if idx == 13:
        # 모든 변수가 할당되었을 때, 방정식 검증
        for eq_name, eq in equations.items():
            total = sum(assigned_values[i] for i in eq['vars'])
            if total != eq['value']:
                return
        total_solutions += 1
        return
    else:
        for num in range(1, 14):
            if not used_numbers[num]:
                assigned_values[idx] = num
                used_numbers[num] = True
                if check_constraints(idx):
                    backtrack(idx + 1)
                assigned_values[idx] = 0
                used_numbers[num] = False

# 초기 검증: E + F + G + H == 91인지 확인
if E + F + G + H != 91:
    print(0)
else:
    backtrack(0)
    print(total_solutions)

 

4. 코드 설명

1. 입력 처리
   • 첫 줄에 A부터 H까지의 값을 입력받습니다.
2. 변수 및 방정식 설정
   • 변수들을 인덱스로 매핑하여 리스트로 관리합니다.
   • 방정식들은 각 방정식마다 포함된 변수들의 인덱스와 필요한 합을 딕셔너리 형태로 저장합니다.
3. 가지치기 함수
   • is_possible(eq_name): 특정 방정식이 현재 상태에서 만족될 수 있는지 확인합니다.
     • 현재까지 할당된 변수들의 합과 남은 변수들의 최소/최대 합을 계산하여 방정식의 값과 비교합니다.
   • check_constraints(var_idx): 특정 변수에 값을 할당한 후, 그 변수가 포함된 모든 방정식을 검사합니다.
4. 백트래킹 함수
   • backtrack(idx): 재귀적으로 변수를 할당하며 가능한 모든 경우를 탐색합니다.
   • 모든 변수가 할당되면 방정식의 값을 정확히 만족하는지 확인하고, 만족하면 해결책 수를 증가시킵니다.
5. 초기 검증
   • 방정식 E+F+G+H=91인지 확인하여 아니면 바로 0을 출력합니다.

 

5. 백준 32825 제출 결과

백준 32825 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다