파이썬 알고리즘 185번 | [백준 3980번] 선발명단 - 브루트포스

Yunny.Log ·2022년 6월 24일

Algorithm

목록 보기

188/318

185. 선발 명단

1) 어떤 전략(알고리즘)으로 해결?

백트래킹 완전탐색 (dfs)

2) 코딩 설명

선수중 아직 선택안됐꼬, 포지션 점수가 0 아닌 애들을 모아모아서 경우를 가지로 파악
total_lis 라는 곳에 모든 경우의 점수를 모아놓고 거기서 최대인 아이를 출력!
주의점은 각 테스트케이스마다 리스트들 초기화해주어야 한다는 것 ^^

<내 풀이>

import sys

def dfs(scr, pos) : # 점수, 몇번째 포지션인지 

    if pos == 11 :
        total_lis.append(scr)

    else :
        for i in range(11) :
            if visited[i] ==0 and people[i][pos]!=0 :
                scr+=people[i][pos]
                visited[i] = 1
                dfs(scr, pos+1) # 다음 경우로 보내버리기 ~ 
                visited[i] = 0 # 방문 원상복귀 
                scr-=people[i][pos] #점수 원상복귀 
                # 처음에 얘를 원상태로 복귀안해줘서 점수가 누적누적 됐었음 ㅋㅋ

c = int(sys.stdin.readline().rstrip()) #test case
# 능력치가 0인 포지션에 배치될 수 없다.



for t in range(c) : 
    pos = [[] for _ in range(11)]
    people =[]

    for i in range(11) :
        # i 번째 선수의 능력치
        people.append(list(map(int, sys.stdin.readline().rstrip().split())))

    total_lis=[]
    scr = 0
    visited = [0]*11

    dfs(0,0)
    print(max(total_lis))

<가로막힌 부분 & 틀렸던 풀이 >

import sys

c = int(sys.stdin.readline().rstrip()) #test case
# 능력치가 0인 포지션에 배치될 수 없다.

pos = [[] for _ in range(11)]
people =[]

for t in range(c) : 
    for i in range(11) :
        # i 번째 선수의 능력치
        people.append(list(map(int, sys.stdin.readline().rstrip().split())))

        for p in range(11) :
            if people[-1][p] !=0 :
                pos[p].append((i,people[-1][p]))

totallis = []

for j in pos :
    print(j)

이와 같이 각 포지션에 배치 가능한 선수들 목록을 빼옴
여기서 고려해야할 것은 한번 택한 선수는 두번 이상 배치되면 안된다는 거지

그럼 일단 여기 pos 에서 선수들 조합만 가지고 생각해보자 . 점수는 사람 구성 경우의 수 구하고 해도 늦지 않지

=> dfs 로 접근하는 것으로 수정 함

dfs 로 수정했는데두 25%에서 틀림 ! ㅇㅁㅇ

import sys

c = int(sys.stdin.readline().rstrip()) #test case
# 능력치가 0인 포지션에 배치될 수 없다.

pos = [[] for _ in range(11)]
people =[]

for t in range(c) : 
    for i in range(11) :
        # i 번째 선수의 능력치
        people.append(list(map(int, sys.stdin.readline().rstrip().split())))

total_lis=[]
scr = 0
visited = [0]*11

def dfs(scr, pos) : # 점수, 몇번째 포지션인지 

    if pos == 11 :
        total_lis.append(scr)

    else :
        for i in range(11) :
            if visited[i] ==0 and people[i][pos]!=0 :
                scr+=people[i][pos]
                visited[i] = 1
                dfs(scr, pos+1)
                visited[i] = 0
                scr-=people[i][pos]

dfs(0,0)
print(max(total_lis))