[SWEA] 1865_동철이의 일 분배 (백트랙킹 이용)

📕 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc&categoryId=AV5LuHfqDz8DFAXc&categoryType=CODE&problemTitle=1865&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

💡 풀이법

1. dfs의 n은 현재 행의 번호이고, items는 현재까지 담당이 지정된 일들의 열값이 담긴 리스트이고, total은 현재까지의 확률이다.

2. 0행부터 dfs를 실행시킨다.

3. 0~N-1까지 for문을 돌면서 i가 items안에 있는 열이 아니면 i를 items안에 넣고 n+1을 해주고, total은 해당 일을 했을 때의 확률을 곱해서 dfs를 돌린다.

(dfs 후에는 다시 items에서 i를 뺴줘야 한다)

4. 만약 진행 중 total이 ans보다 작다면 return을 한다. (가지치기)

5. n 이 N이라면 모든 일의 담당자가 배정된 것이므로 ans와 total을 비교해서 작은 값을 ans에 저장한다.

6. 출력값은 소수점 7번째 자리에서 반올림해서 6째 자리까지만 보이라고 했으므로 반올림해준다.

 

def dfs(n, items, total):
    global ans

    if total <= ans:
        return
    if n == N:
        ans = max(ans, total)
        return

    for i in range(N):
        if i not in items:
            items.append(i)
            dfs(n+1, items, total*(matrix[n][i]/100))
            items.pop()

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    ans = 0
    dfs(0, [], 1)
    print('#{} {:.6f}'.format(tc, round(ans*100,6)))