[D3] SWEA 1244. [S/W 문제해결 응용] 2일차 - 최대 상금

1. 접근 방식

SWEA에서 처음으로 풀어보는 DFS 문제 같다.

숫자를 요리조리 옮기고 관찰해봤으나

어떠한 규칙성도 발견되지 않았다.

그래서, DFS로 접근하기로 했다. 

2. 디테일한 구현

dfs(cnt) -> cnt= 교환 횟수

1) 재귀 함수의 종료 조건

-> 교환 횟수를 다 채웠을 때

 

2) 교환하는 방법

arr[i],arr[j]=arr[j],arr[i]

dfs(cnt+1)

arr[j],arr[i]=arr[i],arr[j]

->돌려놨으면 다시 복구 시켜야한다.

왜냐하면, 다음 줄기에서는 특정 하나의 문자열을 가지고

이중 for문을 계속 도는 형태이여하기 때문이다.

이건 말로 설명하기 어려운데 그림을 그려보면 이해가 갈 것이다.

결국 재귀란 시스템도 규칙과 반복성이다.

 

3. 코드 구현

def dfs(cnt):
    global res
    if cnt==k:
        tmp=''
        for x in arr:
            tmp+=str(x)
       
        if res<int(tmp):
            res=int(tmp)
        return
 
    else:
        for i in range(len(arr)-1):
            for j in range(i+1,len(arr)):
                    arr[i],arr[j]=arr[j],arr[i]
                    tmp=''.join(map(str,arr))
                    if (tmp,cnt) not in ch:
                        ch.append((tmp,cnt))
                        dfs(cnt+1)
                    arr[j],arr[i]=arr[i],arr[j]
 
 
 
 
if __name__=='__main__':
    sys.stdin=open('input2.txt','r')   
    
    
    test_case=int(input()) ## 총 테스트 케이스 개수
   
    for tc in range(test_case):
       s,k=map(str,input().split())
 
       arr=list(map(int,s)) ##문자열
       std=arr[:]
       k=int(k) ##교환 횟수
       res=-1
       ch=[]
       dfs(0)  
       print(f'#{tc+1} {res}')
 

 

 

 

4. 깨달은 점 및 반성

풀이에 성공했으나,

역시나 어려운 것 같다.

그림을 많이 그려보자.