SWEA 1244. 최대 상금 (파이썬)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=PYTHON&select-1=3&pageSize=10&pageIndex=9

SW Expert Academy

 

정답 코드

def dfs(idx, count):
    global res
    #바꾼 횟수 == 입력받은 횟수 일 때
    if count == int(cnt):
    	#기존의 res와 바꾼 직후의 data중 큰 값을 삽입. 이 과정을 통해 최대res값을 매번 갱신
        res = max(int(''.join(data)), res)
        return
    for now in range(idx, len(data)):
        for max_idx in range(now + 1, len(data)):
            if data[now] <= data[max_idx]:
            	#조건이 참일 때 서로를 스왑
                data[now], data[max_idx] = data[max_idx], data[now]
                #dfs함수를 재귀호출하여 count가 입력받은 횟수가 될 때까지 재귀 호출 반복
                dfs(now, count + 1)
                #재귀 호출한 함수가 완전히 return되면 스왑한 숫자판 원상복구
                data[now], data[max_idx] = data[max_idx], data[now]
	
    #res가 갱신되지 않고 dfs를 통해 숫자판을 완전탐색했음에도 입력받은 횟수를 못채웠을 경우
    if not res and count < int(cnt):
    	#잔여횟수의 홀, 짝을 구함
        extra = (int(cnt) - count) % 
        #잔여횟수가 홀수일 경우 
        if extra:
        	#숫자판의 뒤에서 첫번째 요소와 두번째요소를 스왑
            data[-1], data[-2] = data[-2], data[-1]
        dfs(idx, int(cnt))


t = int(input())

for tc in range(1, t + 1):
    data, cnt = input().split()
    data = list(data)
    res = 0
    dfs(0, 0)

    print(f'#{tc} {res}')

숫자판의 모든 요소를 두개씩 비교해야 하므로 이중 for문을 돌린다. 이 때 뒷 요소가 앞 요소보다 크거나 같을 때 입력받은 횟수만큼 스왑하거나 모든 요소를 탐색할 때까지 재귀호출을 반복한다.

이처럼 DFS방식을 활용해서 모든 케이스를 완전탐색할 수 있다.

피드백

처음에 그리디로 접근했다가 한계를 느껴서 다른 사람들의 풀이를 보니 대부분 DFS로 풀었다.

여태까지 DFS, BFS로 풀었던 문제들은 그래프가 주어졌을 때 인접리스트 혹은 인접행렬에 집어넣고 이를 탐색하는 방식이었는데 이번 문제 처럼 그래프가 주어지지 않아도 응용해서 풀 수 있다는 걸 알 수 있었다.