[Python/DailyAlgo] 97. N-Rook Problem

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

순열과 조합

https://dailyalgo.kr/ko/problems/97

---

풀이

def solution(n):

# 입력 : 체스판의 크기 n x n이자 룩의 개수인 n
# 출력 : 조건에 맞게 n개의 룩을 배치 가능한 경우의 수
# 조건 : n개의 룩은 체스판 위에서 공격 불가,
# 행 번호와 열 번호가 같은 곳(i == j)에는 룩을 둘 수 없음.

# 엥... 이거 사실상 순열조합 문젠데?
# 01234 란 놈을 높이로 정해놓고,
# 이걸 가로로 가지고 순열을 돌리면 될거같은데?
# '높이'가  저 놈들을 unique하게 만들어주고, 따라서 중복 없이 순서를 고려해야 함.
# 근데, numbers[index] = index 인 경우는 생략해야함. 
# numbers = 13240라 하면, numbers[2] = 2니까. 
# 즉, 3P3 - 가운데 경우.
# 가운데 경우는, 하나 잡고 그거 포함이면서 나머지 아무렇게나, 그거 미포함하면서 나머지 중 하나 걸리게.
# 전자는 

    def permutation(current):
        for i in range(len(current)):
            if current[i] == i:
                return
        if len(current) == n:
            answer.append(current[:])
            return
        for i in range(n):
            if not visited[i]:
                visited[i] = True
                current.append(i)
                permutation(current)
                visited[i] = False
                current.pop()



    answer = []
    visited = [False] * n
    permutation([])
    return len(answer)

이 문제는, 위에서부터 한 층 뽑고 한 층 뽑고 하면, 그래프(트리) dfs 모양이며 좀 더 들어가면 순열임을 알 수 있음.

이 룩의 특성 자체가 visited를 의미함. 그 열 자체를 다 막아버리는 거니까. 그리고 중복 허용 안하고 앞에서부터 순서 고려해서 뽑으니까.

강사님 풀이 확인)

def solution(n):

    # 우리가 기존에 구현했던 것들과 달리, 우리는 경우의 수만 세면 됨.
    # 즉, 빈 리스트를 넣어가면서 매 재귀 단계에 다 고려해줄 필요가 없음.
    # 따라서 여기선 매개변수로 단계(즉, 행의 번호, 층의 번호)만 넣으면 됨.
    def permutations(row):
        # 재귀는 종료조건과 점화식으로 나누어짐.

        # 종료조건 1: 모든 행에 대해 룩을 선택헀을 때 결과 + 1 후 반환
        if row == n:
            nonlocal counts
            counts += 1
            return
        # 2. 점화식: 맨 처음 열부터 룩이 없는 열을 선택해서, 재귀를 진행
        for col in range(n):
            if row != col and visited[col] == False:
                visited[col] = True
                permutations(row + 1)
                visited[col] = False

    visited = [False] * n
    counts = 0
    permutations(0)

    return counts

 

이거 순열의 매개변수에 row를 쓴 기법 잘 기억하기.

---

250223 재풀이

정석(백트래킹을 넣기 전에 미리 함)

시간복잡도 O(n!)

def solution(n):

    # 입력 : n x n 크기 체스판의 크기 n
    # 순열!! nPn but 여기서 i == j인 경우는 바로 return(백트래킹)
    def permutations(row):
        # 1. 만약 뽑을 만큼 뽑았다면 종료
        if row == n:
            nonlocal counts
            counts += 1
            return
        # 2. 그렇지 않다면, 재귀 돌며 계속 뽑음
        for col in range(n):
            if not visited[col] and col != row:
                visited[col] = True
                permutations(row + 1)
                visited[col] = False

    visited = [False] * n
    counts = 0
    permutations(0)
    return counts

궁금해서, 억지로 매개변수로 리스트 하나만 써서 풀어봄(백트래킹o)

시간복잡도 O(n!)

def solution(n):

    # 입력 : n x n 크기 체스판의 크기 n
    # 순열!! nPn but 여기서 i == j인 경우는 바로 return(백트래킹)
    def permutations(current):
        # 백트래킹
        if current:
            if current[-1] + 1 == len(current):
                return
        # 1. 만약 뽑을 만큼 뽑았다면 종료
        if len(current) == n:
            nonlocal counts
            counts += 1
            return
        # 2. 그렇지 않다면, 재귀 돌며 계속 뽑음
        for i in range(n):
            if not visited[i]:
                visited[i] = True
                current.append(i)
                permutations(current)
                visited[i] = False
                current.pop()

    visited = [False] * n
    counts = 0
    permutations([])
    return counts

궁금해서, 억지로 itertools 모듈 써서도 풀어봄(백트래킹 x)

백트래킹을 쓰지 않아, 시간복잡도 O(n! * n)으로 매우 비효율적.

from itertools import permutations
def solution(n):

    answer = []
    for perm in permutations(range(n), n):
        for i in range(n):
            if perm[i] == i:
                break
        else:
            answer.append(perm)

    return len(answer)
    # 궁금해서 억지로 itertools 모듈 써서 풀어본 풀이(백트래킹 x)
    # 시간복잡도 O(n! * n)
    # 최악의 경우, n!개의 경우의 수에 대해 각각 길이 n짜리 탐색을 하기 때문.