🥇[백준] 1759 암호 만들기 (골드5) / 백트래킹

문제요약

나의 코드 및 설명

• 모음과 자음 리스트를 만들어 놓고, dfs를 통해 l의 길이를 갖는 temp_list가 호출이 되었을 때, 모음 개수와 자음 개수를 체크하여 조건에 맞다면 ans에 추가한다.

def dfs(count, start, temp_list):
    if len(temp_list) == l: #temp_list 길이가 l에 도달한다면
        mo_cnt = 0
        za_cnt = 0
        for i in temp_list:
            if i in mo: #모음 개수 체크
                mo_cnt += 1
            if i in za: #자음 개수 체크
                za_cnt += 1
        if mo_cnt >= 1 and za_cnt >= 2:
            ans.append(temp_list) #조건에 맞다면 ans에 추가
    if count == c:
        return
    
    #for문의 시작점을 start로 정해놓고
    #하위 함수 호출 시 start+1을 받아서 중복되지 않게 만듬
    for i in range(start, len(pw_list)): 
        dfs(count+1, i+1, temp_list+[pw_list[i]])

l, c = map(int, input().split())
pw_list = list(map(str, input().split()))
pw_list.sort()
mo = []
za = []
for i in pw_list:
    if i in ['a','e','i','o','u']:
        mo.append(i) #모음 리스트 생성
    else:
        za.append(i) #자음 리스트 생성
ans = []

dfs(0,0,[])
for i in ans:
    print("".join(map(str, i)))

피드백

근래에 백트래킹 문제를 많이 풀어보았더니 골드 문제임에도 불구하고 어렵지 않게 풀 수 있었다. 그러나 아직도 헷갈리는 것은 백트래킹 함수 작성 시 'shallow copy'에 대한 문제이다. 아직 완전히 이해는 되지 않지만 그래도 여러 문제를 풀어보면서, 내 나름대로 함수의 변수에 리스트를 직접 넘겨주어 조건에 충족했을 시 ans에 저장하고, pop() 메서드를 쓰지 않는 방식으로 하면 'shallow copy'를 피할 수 있다라는 것을 체감하였다. 앞으로 많은 문제를 풀어보며 완벽히 이해할 수 있도록 노력해야겠다.