Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 도미노

[도미노]

접근 과정

• $N \times N$크기의 보드에서, $N$개의 도미노를 고를 때 선택한 도미노들이 서로 같은 행, 같은 열에 있으면 안 된다. 마치 체스에서의 룩이 서로 공격할 수 없는 위치에 놓이는 것을 상상하면 된다.
• 이러한 조건 덕분에, $N!^2$ 개의 모든 경우를 고려할 필요 없이, 선택한 $N$개의 도미노의 사이클과 그룹에 대해서만 생각해 주면 된다.
  • 서로 같은 행, 같은 열에 있으면 안되므로 이 도미노들의 인덱스는 distinct integer로 구성되어있음을 생각할 수 있다.
  • 따라서, permutations를 이용하여 구간 $[0, N)$ 의 정수를 원소로 갖는 $_nP_n = n!$개의 순열을 만든다. 이는 주어진 $N$에 대해 가능한 모든 사이클을 의미한다.
  • 예를 들어 생각해 보면, 다음과 같다.
    • $N=5$일 때의 순열 중 하나인 [2, 4, 1, 3, 0] 에 대해 생각해 보자.
    • 첫 번째 원소([0])의 값인 $2$는 그 다음 인덱스를 의미한다.
    • [2]의 값인 $1$은 그 다음 인덱스를 의미한다.
    • [1]의 값인 $4$는 그 다음 인덱스를 의미한다
    • [4]의 값인 $0$은 그 다음 인덱스인데, 이는 시작 인덱스([0])과 동일하므로 이렇게 네 원소가 하나의 사이클 그룹을 이룸을 알 수 있다.
    • 왼쪽에서 시작하여 탐색하지 않았던 다음 원소([3])에 대해서도 같은 방식으로 생각해 주면, [3]의 값인 $3$은 자기 자신을 가리키므로 이 또한 길이가 1인 사이클임을 알 수 있다.
    • TMI) 이를 수학적으로 나타내면 다음과 같다. Cauchy’s two-line notation에 따르면, $S=\{2, 4, 1, 3, 0\}$, $\sigma(0)=2, \sigma(1)=4, ..., \sigma(4)=0$이고,
      $\sigma = \begin{pmatrix} 0 & 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 & 0 \end{pmatrix}$
      이다. Cycle notation으로 나타내면, $\sigma = (0214)(3)=(0214)$로 나타낼 수 있다.
      
• 가능한 모든 사이클에 대해 각각 점수를 계산하여 최댓값과 최솟값을 계속해서 갱신해 나간다. 이 때, 사이클 그룹의 개수가 짝수일 땐 점수에 $-1$을 곱해야 함에 유의해야 한다.

Solution. Brute-force + Backtracking $O(n \cdot n!)$

import sys
input = sys.stdin.readline
from itertools import permutations

def convert(c):
    if c.isalpha(): return -(ord(c)-64)
    return int(c)

def score(cycle):
    used = set()
    sign = -1
    ret = 1

    for i in range(n):
        if i not in used:
            sign *= -1
            j = i
            while j not in used:
                used.add(j)
                ret *= board[j][cycle[j]]
                j = cycle[j]
    
    return sign*ret

n = int(input())
board = [[*map(convert, input().rstrip())] for _ in range(n)]

mx, mn = -1000000, 1000000
for cycle in permutations(range(n)):
    cur = score(cycle)
    mx = max(mx, cur)
    mn = min(mn, cur)

print(mn, mx, sep='\n')

• 'A' 부터 'I' 까지의 문자가 의미하는 것은 $-1$부터 $-9$이므로, 입력받은 문자가 알파벳이라면 -(ord(c)-64)로, 그렇지 않다면($0$부터 $9$까지의 수라는 것이므로) 정수로 변환하는 함수를 만들었다.
• 모든 사이클 순열을 만들기 전에 점수의 최댓값과 최솟값을 충분히 작은 값/큰 값으로 초기화해 놓는다. $\pm (9^6+1)$이나 float('inf') 도 있지만 나이브하게 $10^6$으로 잡았다.
• score()함수는 만들어진 사이클에 대해 각 도미노에 쓰여 있는 수를 곱해나가 점수를 계산하는 함수이다.
  • 먼저 sign의 역할은 return할 점수의 부호이다. 사이클 그룹의 개수를 누적시킨다음 1 if cnt%2 else -1을 이용하는 방법도 있겠으나, 부호만 바뀐다는 점에 착안하여 조금 더 직관적이진 않을까 싶어 위와 같이 짰다. 지금 생각해보니 두 방법 모두 일장일단이 있는 것 같다.
  • 순열 사이클의 첫 번째 요소부터 탐색을 시작한다. 탐색하지 않은 요소라면 그 요소와 사이클을 이루는 모든 요소들에 대해 탐색하며 점수를 계산해 나가고, 사용 처리를 한다. 그러다가 이미 사용한 원소를 만났다는 것은, 한 사이클 그룹에 대한 탐색이 끝났다는 것이므로 탐색하지 않은 다음 원소에 대해 전체를 다 탐색할 때까지 반복적으로 탐색해 나간다.
  • 위에서 예시로 들었던 순열 $S = \{2, 4, 1, 3, 0\}$에 대해 생각해 보면, 이는 이 문제에서 $board[0][2] \rightarrow board[2][1] \rightarrow board[1][4] \rightarrow board[4][0]$, $board[3][3]$ 이 된다. ($\because$ $[i][j]$에서 도미노 A의 두 번째 숫자($j$)와 B의 첫 번째 숫자($i$) 가 같으면 된다고 했으므로)

Permutations

def permutations(n):
    ret = []
    used = set()

    def _perm(p=[]):
        if len(p) == n: ret.append(p[:]); return
        
        for i in range(n):
            if i not in used:
                p.append(i)
                used.add(i)
                _perm(p)
                used.discard(i)
                p.pop()
    
    _perm()
    return ret

• itertools.permutations(range(n))과 같은 역할을 하는 코드를 직접 구현했었다.
• 하지만 itertools가 워낙 빠르므로… 공부할 겸 처음 제출할 땐 직접 permutations를 짰고, AC 받은 뒤엔 itertools로 다시 제출했다.

---

References

• Groupprops, Cycle decomposition for permutations

  • Groupprops, Cycle decomposition theorem for permutations (Proof)

• Wikipedia, Permutation