[SWEA][D4] 1865.동철이의 일 분배 DFS 파이썬

 

📌 문제출처 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc&categoryId=AV5LuHfqDz8DFAXc&categoryType=CODE

📖 1865. 동철이의 일 분배 D4   동철이가 차린 전자회사에는 N명의 직원이 있다. 그런데 어느 날 해야할 일이 N개가 생겼다. 동철이는 직원들에게 공평하게 일을 하나씩 배분하려고 한다. 직원들의 번호가 1부터 N까지 매겨져 있고, 해야 할 일에도 번호가 1부터 N까지 매겨져 있을 때, i번 직원이 j번 일을 하면 성공할 확률이 Pi, j이다. 여기서 우리는 동철이가 모든 일이 잘 풀리도록 도와주어야 한다. 직원들에게 해야 할 일을 하나씩 배분하는 방법은 여러 가지다. 우리는 여러 방법 중에서 생길 수 있는 “주어진 일이 모두 성공할 확률”의 최댓값을 구하는 프로그램을 작성해야 한다. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1 ≤ N ≤ 16)이 주어진다. 다음 N개의 줄의 i번째 줄에는 N개의 정수 Pi, 1, … , i, N(0 ≤ Pi, j ≤ 100)이 주어진다. Pi, j는 i번 사람이 j번 일을 성공할 확률을 퍼센트 단위로 나타낸다. [출력] 각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 모든 일을 성공할 확률이 최대화될 때의 확률을 퍼센트 단위로 소수점 아래 7번째 자리에서 반올림하여 6번째까지 출력한다. [예제 풀이] 첫번째 직원이 첫번째 일을 담당하고, 두번째 직원이 두번째 일을 담당하고, 세번째 직원이 세번째 일을 담당할 때 모든 일을 성공할 확률이 최대가 되고 그 확률은 (0.13*0.7*1.0)*100 = 9.1%가 된다.

아직도 잘 못짜는 어려운 DFS... 눙물...

해설  [SWEA][D4] 1865. 동철이의 일 분배 D4 파이썬

< 구조 >  * DFS 재귀방식 활용하기

 

D4부터는 시간복잡도를 따지도록 입력값의 크기를 이제 유심히 봐야 한다.

입력1 : 하나의 정수 N(1 ≤ N ≤ 16) 로 깊이를 들어가게 되고

입력2 : N개의 줄의 i번째 줄에는 N개의 정수 P(i, 1), … , P(i, N)(0 ≤ P(i, j) ≤ 100)

=> 즉N*N의 2차원 배열로 입력을 받아보면

한 줄에서 하나씩 골라서 N개 까지 가는 경우가, 최악으로 16!(20조 개수)가 되므로 다 계산하고 돌리고 있음 안된다.

 

즉, 다 끝까지 골라서 계산하지 말고 가망 없으면 계산을 중지하는 노선이 있도록한다.

<주의>

(중간 혹은 최종)result <=  (최종)max_result: (O) 작성하여함.

(중간 혹은 최종)result < (최종)max_result (X) 하면 더 볼 것을 많이 줄이지 못해 타임에러

(중간)result == (최종)max_result 은 상황은 이미 단계를 진행할 필요가 없는 것이므로,

이는 수학적 상식이 필요한데, 1에서 0.XX를 곱하면 수가 점점 0 에 가까워진다.

(즉, 뭔가(0.XX)를 곱할 수록 크기가 계속 작아진다.)

 

<조건으로 구조 짜기에서>

예시의 3명의 직원이 3가지의 일을 각각 골라할 떄, 그 확률은 (0.13*0.7*1.0)*100 = 9.1%

설명 대로 처음부터 배열 값에 0.01을 곱하고 처리하고 마지막 확률 출력할 떄만 100을 곱해도 될 듯!

 

<마지막 출력>

모든 일을 성공할 확률이 최대화될 때의 확률을 퍼센트 단위로 소수점 아래 7번째 자리에서 반올림하여 6번째까지 출력

응... ㅠㅠ

그냥 100곱해서 % 로 변환해보니, 제멋대로 길이가 나옴 #1 49.65456 #2 23.362170493453508 #3 32.0 #4 33.8044889479752 #5 16.695905072994208 #6 14.878080000000002 #7 4.559359807780806 #8 7.764233056568767 #9 26.789665667154427 #10 76.56

소수점 아래 7번째 자리에서 반올림하여 6번째까지 #1 49.654560 #2 23.362170 #3 32.000000 #4 33.804489 #5 16.695905 #6 14.878080 #7 4.559360 #8 7.764233 #9 26.789666 #10 76.560000

 

💡<코드 설명>

def workpower(result, person): # result: 확률 계산해가는 값 , person:깊이,i번째사람
    global max_result
    global visited
    # 끝까지 계산하지 않고 하는 도중에 가망이 없을 때... 
    # (**1미만을 곱하면 점점 작아지니깐) 끝까지 더 가지 말고 돌아간다.
    # N<=16이므로 최악 16!까지 가는 것을 사전에 방지하는 작업!!!
    # 주의!!!:: (중간 혹은 최종)result < (최종)max_result 하면 볼 것을 많이 줄이지 못해 타임에러
    # (중간)result == (최종)max_result 은 상황은 이미 단계를 진행할 필요가 없는 것임.
    if result <= max_result:
        return
    # 기본파트, 깊이 제일 밑 끝
    if person == N: # 모든 직원이 각 자 일을 맡아 다 할때, 최종결과랑 비교
        if max_result <= result:
            max_result = result
        return
    # 재귀파트    
    for j in range(N): # 전체를 도는데
        if visited[j] == 0: # 방문을 안했으면
            visited[j] = 1 # 방문한다
            workpower(result*arr[person][j]*0.01, person+1) # 재귀 DFS
            visited[j] = 0 # 방문다했다
  
T = int(input())
for t in range(1, T+1):
    N = int(input()) # N개의 행:N인원수 열:N개의 일 능률 
    arr = [list(map(int, input().split())) for _ in range(N)]
    visited = [0] * N 
    max_result = 0 # 비교할 최대 확률(0%가 가장 낮으므로)
    # result: 확률 계산할 초기값은 1(~0.00까지 계속 작아질 예정) , person:깊이는 0부터 N까지 1씩 증가할 예정
    workpower(1, 0) 
    # 표현 1 # 소수6번째자리까지(7번째에서 알아서 반올림됨다) 신기해...ㅋㅋㅋ 문법인가보다...
   final_result = format(max_result*100, '.6f')
    print(f'#{t} {final_result}')
    # 표현 2
    print('#{} {:.6f}'.format(t,max_result*100))