3980. [Python]선발 명단

1. 문제

 

https://www.acmicpc.net/problem/3980

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• 백트래킹
• 브루트 포스

 

3. 파이썬 코드

 

import sys

input = sys.stdin.readline
# 백트래킹
def DFS(start):
    # 최대값 저장
    global max_value
    # 값 저장
    global value
    # 최종 11에 도달했을 때
    if start == 11:
        # 최대 값보다 값이 크면 갱신
        if max_value < value:
            max_value = value
        return
    # 11명의 포지션 바복
    for j in range(11):
        # 포지션 값이 0 이 아니고 방문안했을 경우
        if position[start][j] != 0 and pos_visited[j] == False:
            # 방문 처리 후 값 더해주고 재귀 실행 백트래킹
            pos_visited[j] = True
            value += position[start][j]
            DFS(start+1)
            value -= position[start][j]
            pos_visited[j] = False

T = int(input())
# 테스트 케이스 반복문 만큼 진행
for _ in range(T):
    # 포지션별 리스트 추가
    position = []
    for _ in range(11):
        position.append(list(map(int,input().split())))
    # 최대값 기본 값
    max_value = 0
    value = 0
    # 방문처리 체크
    pos_visited = [False] * 11
    # 백트래킹
    for i in range(11):
        if position[0][i] != 0:
            pos_visited[i] = True
            value += position[0][i]
            DFS(1)
            value -= position[0][i]
            pos_visited[i] = False
    print(max_value)

 

4. 문제를 풀고난 후 생각

 

• 모든 경우의 수를 다 탐색하면서 알고리즘을 돌리면 된다.
• 백트래킹을 진행하되 0 번인덱스를 기준으로 백트래킹을 해주면 원하는 결과값이 나온다.
• 테스트 케이스 개수가 따로 명시되어있진 않았고 인풋이 많을 것 같아서 sys.stdin.readline 처리를 해줬다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 브루트 포스
• 백트래킹