99클럽 코테 스터디 36일차 TIL, 백준 / 도미노 / 1552

🔑 오늘의 학습 키워드 dfs

🔗 문제링크 https://www.acmicpc.net/problem/1552

 

import itertools

# 알파벳을 숫자로 변환하는 함수
def alphabet_to_minus_num(c):
    if c.isdigit():
        return int(c)
    else:
        return -1 * (ord(c) - ord('A') + 1)

# 점수를 계산하는 함수
def calculate_domino_cross(cycles, domino):
    score = 1
    for cycle in cycles:
        cycle_score = 1
        for (i, j) in cycle:
            cycle_score *= domino[i][j]
        score *= cycle_score
    if len(cycles) % 2 == 0:
        score *= -1
    return score

# 모든 가능한 순열을 생성하여 최대 및 최소 점수를 찾는 함수
def find_cycle(N, domino):
    indices = list(range(N))
    global answer_min, answer_max
    answer_min, answer_max = float('inf'), float('-inf')

    for rows in itertools.permutations(indices):
        cycles = []
        visited = [False] * N
        for i in range(N):
            if not visited[i]:
                cycle = []
                x = i
                while not visited[x]:
                    visited[x] = True
                    cycle.append((x, rows[x]))
                    x = rows[x]
                cycles.append(cycle)

        score = calculate_domino_cross(cycles, domino)
        answer_min = min(answer_min, score)
        answer_max = max(answer_max, score)

    return answer_min, answer_max

# 입력 처리 및 함수 호출
def main():
    N = int(input())
    domino = []
    for _ in range(N):
        domino.append([alphabet_to_minus_num(c) for c in input().strip()])

    answer_min, answer_max = find_cycle(N, domino)
    print(answer_min)
    print(answer_max)

# 함수 실행
main()

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

'''

싸이클을 만들어서 그 값들을 곱해나감

싸이클이란

N ^ 2 보드판, N개 선택 -> 같은 열이나 행에는 존재하면 안됨 ( Queen 같은 느낌 )

1 <= N <= 6

-> 대각선은 그냥 자기 자신이 1개의 싸이클

# 싸이클이 만들어지는 경우 (N = 5)

1. (i,i) 대각선인 경우

2. (i,j) , (j,i) 인 경우

3. 1,2번을 제외한 경우에서 선택해나가면서 싸이클을 생성하는 경우

(그런데 여기서 같은열과 행을 제외해야하니깐 실제로 생성되는 경우는 많이 없을지도?)

-> 맨 위 한 행에 대해서만 백트래킹하면서 찾으면 되는 것 같음

N = 1 : 1

N = 2 : 2

N = 3 : 6

구하려는 것 : 곱한 값들의 최대 최소 (마이너스 존재)

싸이클 그룹 개수 짝수 -> * -1

알고리즘

1. 브루트 포스로 싸이클이 가능한 경우 계산

2. 최대 최소 값 갱신해 나감

'''

 

😎 알고리즘 개요

틀린풀이

import sys
input = sys.stdin.readline

from collections import deque

N = int(input())
domino =[]
global answer_min,answer_max
answer_min = float('inf')
answer_max = -float('inf')

def alphabet_to_minus_num(input_list):
    num_list = []
    for domino_back in input_list:
        if not domino_back.isdigit(): num_list.append(64-ord(domino_back)) # A -> 65 -> -1
        else : num_list.append(int(domino_back))
    return num_list

for _ in range (N):
    tmp = list(input().strip())
    domino.append(alphabet_to_minus_num(tmp))
    
def is_cycle_num_even(made_list):
    visited = [False] * len(made_list)
    cycle_count = 0
    for i in range(len(made_list)):
        if not visited[i]:
            cycle_length = 0
            current = i
            while not visited[current]:
                visited[current] = True
                current = made_list[current]
                cycle_length += 1
            if cycle_length % 2 == 0:
                cycle_count += 1
    return cycle_count % 2 == 1  # 짝수 사이클의 개수가 홀수인 경우 True 반환

def calculate_domino_cross(made_list):
    global answer_min, answer_max
    this_case_cross = 1
    for i, j in enumerate(made_list):
        this_case_cross *= domino[i][j]
    
    if is_cycle_num_even(made_list):
        this_case_cross *= -1
    
    answer_max = max(answer_max, this_case_cross)
    answer_min = min(answer_min, this_case_cross)

def find_cycle(domino,made_list):
    if len(made_list) == N:
        calculate_domino_cross(made_list)
        return
    
    for i in range (N):
        if not used[i] and i != domino:
            used[domino] = True
            made_list.append(i)
            find_cycle(i,made_list)
            made_list.pop()
            used[domino] = False

used = [False] * N
for i in range(N):
    find_cycle(i,[i])

print(answer_min)
print(answer_max)

 

✅ 오늘의 회고

 

- 포기 했다..

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL