파이썬으로 n×n 체스판에 룩을 서로 공격하지 않게 배치하는 경우의 수 구하기

문제 개요

크기가 n × n인 체스판이 주어졌다고 가정해 보겠습니다. 이때 n개의 룩(rook)을 배치하되, 어떤 룩도 다른 룩을 공격할 수 없도록 하는 배치 방법의 수를 구해야 합니다.

룩은 같은 행(row) 또는 같은 열(column)에 있는 기물을 공격할 수 있습니다. 따라서 모든 룩이 서로 다른 행과 서로 다른 열에 위치해야 합니다. 또한 두 가지 배치 방법 중 어느 하나라도 특정 칸의 점유 여부가 다르다면, 그 두 방법은 서로 다른 것으로 간주합니다.

예를 들어 입력값이 3이라면, 출력은 6이 됩니다.

풀이 접근 방법

핵심 아이디어는 매우 간단합니다. n개의 룩이 서로 공격하지 않으려면 각 행과 각 열마다 정확히 하나의 룩만 존재해야 합니다.

첫 번째 행에서 룩이 놓일 수 있는 열은 n가지입니다. 두 번째 행에서는 이미 사용된 열을 제외한 (n−1)가지, 세 번째 행에서는 (n−2)가지, 이런 식으로 선택지가 줄어들어 마지막 행에는 단 1가지만 남습니다.

따라서 전체 경우의 수는 다음과 같습니다.

n × (n−1) × (n−2) × ... × 1 = n!

즉, 정답은 n의 팩토리얼(n!)입니다. 이는 n개의 열에 대한 순열(permutation)의 개수와 정확히 일치합니다.

구현 코드

파이썬의 math 모듈에 내장된 factorial 함수를 활용하면 손쉽게 해결할 수 있습니다.

import math

class Solution:
   def solve(self, n):
      return math.factorial(n)

ob = Solution()
print(ob.solve(3))

입력

3

출력

6

복잡도 분석

math.factorial 함수는 O(n) 시간에 계산되므로, 이 풀이의 시간 복잡도는 O(n)입니다. 다만 n이 커질수록 결과값이 매우 빠르게 증가하므로, 파이썬처럼 임의 정밀도 정수를 지원하는 언어에서는 문제없지만 고정 크기 정수형을 사용하는 언어에서는 오버플로우에 유의해야 합니다.