[Python/DailyAlgo] 112. N-Rook Problem 2

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

문제 유형 보기

순열과 조합

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

---

풀이

def solution(board):

    # 입력 : 각각의 칸에 숫자가 배정되어있는 행렬 board
    # 출력 : 룩을 여러가지 경우의 수로 놓을 수 있잖음?
    # 이 때의 룩들이 놓인 칸의 숫자 합이 최대인 경우를 반환

    # 이거, max_score 변수 하나 둔 다음에, max(max_score, cur_score) 하면 되겠는데?
    # 그러면, 순열의 매개변수로 max_score 변수를 넣어주면 될듯? 직접 써먹을 거니까!
    # 그리고, max_score 초기값 0으로 하면 될듯

    # 매개변수는 max_score랑 row 두개만 두면 되겠는데?
    # row나 current 둘 중 하나를 매개변수로 넣어줘야 현재 단계를 셀 수 있는데,
    # 이 문제는 그냥 row만 써도 됨.

    def permutations(row, cur_score):
        nonlocal max_score
        max_score = max(max_score, cur_score)
        
        # 종료조건이랑 점화식! 기억하자.
        if row == n:
            return

        # 점화식 : 다음 행으로 넘어가면서 계속 순열 돌리기
        for col in range(n):
            if not visited[col]:
                visited[col] = True
                # 걍 현재칸을 추가
                permutations(row + 1, cur_score + board[row][col])
                visited[col] = False
        


    n = len(board)
    visited = [False] * n
    max_score = 0
    permutations(0, max_score)
    return max_score

강사님 풀이 확인)

어차피 다 고르고 점수비교하면 되니까, 점수비교를 n일 때만 하면 됐었네!!

def solution(board):

    # 입력 : 각각의 칸에 숫자가 배정되어있는 행렬 board
    # 출력 : 룩을 여러가지 경우의 수로 놓을 수 있잖음?
    # 이 때의 룩들이 놓인 칸의 숫자 합이 최대인 경우를 반환

    # 이거, max_score 변수 하나 둔 다음에, max(max_score, cur_score) 하면 되겠는데?
    # 그러면, 순열의 매개변수로 max_score 변수를 넣어주면 될듯? 직접 써먹을 거니까!
    # 그리고, max_score 초기값 0으로 하면 될듯

    # 매개변수는 max_score랑 row 두개만 두면 되겠는데?
    # row나 current 둘 중 하나를 매개변수로 넣어줘야 현재 단계를 셀 수 있는데,
    # 이 문제는 그냥 row만 써도 됨.

    def permutations(row, cur_score):
        
        # 종료조건이랑 점화식! 기억하자.
        if row == n:  
            nonlocal max_score
            max_score = max(max_score, cur_score)
            return

        # 점화식 : 다음 행으로 넘어가면서 계속 순열 돌리기
        for col in range(n):
            if not visited[col]:
                visited[col] = True
                # 걍 현재칸을 추가
                permutations(row + 1, cur_score + board[row][col])
                visited[col] = False

    # 열을 뽑는 경우의 수
    n = len(board)
    # 열을 뽑는 방문 배열
    visited = [False] * n
    max_score = 0
    permutations(0, max_score)
    return max_score

 

 

---

250223 재풀이

def solution(board):
    
    # 얘는 백트래킹은 x. 일단 전체 경우의 수는 n!이 맞음 순열.
    # 모든 경우의 수 n!을 다 돌긴 돌아야겠는데?
    # 다 돌고, 마지막에 max_score랑 비교해 max 갱신하면 됨.

    def permutations(row, score): # cumulative score
        # 1. 뽑을 만큼 뽑았으면 종료
        if row == n:
            nonlocal max_score
            max_score = max(max_score, score)
            return
        # 2. 그렇지 않다면, 재귀를 계속 돌며 수를 더 뽑음.
        for col in range(n):
            if visited[col] == False:
                visited[col] = True
                permutations(row + 1, score + board[row][col])
                visited[col] = False

    n = len(board)
    visited = [False] * n
    max_score = 0
    permutations(0, max_score)
    return max_score