[백준] [Python] 1759번 암호 만들기 - 백트래킹

www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

 

 

Python

 

1. abcd bacd 처럼 visit 리스트는 일치하지만 정렬되지 않은 문자 거르기

단어 전체 길이을 추적하기 위한 k 변수 외에

처음 받은 배열에서 현재 사용한 문자의 위치를 저장해주는 next를 생성

for문은 k부터 시작하는 것이 아니라 next부터 시작하여 정렬 및 중복 예방

import sys
l, c = map(int, sys.stdin.readline().split())
arr = sys.stdin.readline().split()
arr.sort()
visit = [0]*c
word = []

# v == vowel

# next를 두어 순서가 뒤집히지 않도록 함
def back(k, next, v, ccnt):
    if k == l:
        if v and ccnt > 1:
            print(''.join(word))
        return

    for i in range(next, c):
        if visit[i] == 0:
            visit[i] = 1
            word.append(arr[i])

            # ccnt와 v를 바꾸면 이후에 되돌려줘야 하기 때문에
            # 함수 실행 시에 덧셈을 해주어 원래 값 유지
            if not v or ccnt < 2:
                if arr[i] in 'aeiou':
                    back(k+1, i+1, 1, ccnt)
                else:
                    back(k+1, i+1, v, ccnt+1)
            else:
                back(k+1, i+1, v, ccnt)
            visit[i] = 0
            word.pop()


back(0, 0, 0, 0)

 

 

2. 자음 개수 = 전체 - 모음

그러므로 자음 개수만 추적하면 된다

import sys
l, c = map(int, sys.stdin.readline().split())
arr = sys.stdin.readline().split()
arr.sort()
visit = [0]*c
word = []


def back(k, next, v):
    if k == l:
        if v and len(word)-v > 1:
            print(''.join(word))
        return

    for i in range(next, c):
        if visit[i] == 0:
            visit[i] = 1
            word.append(arr[i])

            # 자음 = 전체 - 모음
            if arr[i] in 'aeiou':
                back(k+1, i+1, v+1)
            else:
                back(k+1, i+1, v)
                
            visit[i] = 0
            word.pop()


back(0, 0, 0)