[SWEA/D3] 1244 최대 상금 / 백트래킹

문제 바로가기

SW Expert Academy

나의 코드 및 설명

• dfs 함수 : 2중 for문을 통해 두 개의 숫자판을 선택한 후, 목표 교환 횟수만큼 dfs를 수행했다면 변수에 저장된 prize 리스트를 숫자화시키고 이전의 최댓값과 비교하여 리턴한다.
• 위와 같이 풀이한다면 시간 초과가 발생한다. 시간 초과를 피하기 위해서는 가지치기(중복 제거)를 해줘야 하는데, 방법은 아래와 같다.
• 메인 함수에 룩업테이블인 visited 리스트를 생성하고, 숫자판 교환을 끝낸 숫자리스트가 visited에 없다면 append 해주어 방문 처리 해주면 된다. 이 때, dfs 함수 호출 번호를 표시하기 위해, dfs 함수의 변수인 count도 같이 visited 리스트에 방문 처리 해준다. 
  (두 번째 dfs 함수 호출의 82388이 방문체크 되어있다면, 두 번째 dfs 함수 호출 때의 82388은 그냥 통과한다.)

def dfs(count, prize):
    global ans
    if count == total: #교환횟수에 도달했다면
        #최대값 확인
        ans = max(ans, int("".join(map(str, prize))))
        return
    
    for i in range(len(num_list)-1): #먼저 숫자판 하나를 선택
        for j in range(i+1, len(num_list)): #남은 숫자판 중 하나를 선택
            num_list[i],num_list[j] = num_list[j],num_list[i] #선택한 숫자판 교환
            #중복 제거하기 위해(같은 dfs함수 내 82388과 82388은 동일할 경우 통과)
            #check 임시 변수 생성
            check = int("".join(map(str, num_list))) 
            #dfs함수 번호(count)와 숫자 정보(check)가 visited 리스트에 없다면
            if (count,check) not in visited:
                #visited에 dfs함수 번호(count)와 숫자 정보(check) 추가
                visited.append((count,check))
                #방문 체크 안되어있다면 다음 dfs함수 호출
                dfs(count+1, num_list)
            #다녀 와서는 바꿔놓은 숫자판 원상복귀
            num_list[i],num_list[j] = num_list[j],num_list[i]
            

t = int(input())
for test_case in range(1,t+1):
    num, total = map(int ,input().split())
    num_list = list(map(int,str(num)))
    visited = []
    ans = 0
    dfs(0,[])
    print("#{} {}".format(test_case, ans))

피드백

접근 방법도 몰랐고, 이해하기도 어려웠던 문제. 처음엔 단순 구현으로 풀이하려다가 TC 15개 중 10개만 통과하게 되어 다른 방법을 생각하게 만든 문제이다. 이 문제 덕분에 백트래킹, DFS, BFS에 대한 추가적인 공부를 할 수 있었다. 참 고마운 문제이다. 추가적인 공부를 하고 와서, 정답 판정을 받을 수 있었다.