티스토리 뷰

백준 스터디

백준 1759번 – 암호 만들기 (Python)

박완희버서커 2025. 7. 31. 21:23

백준 1759번 – 암호 만들기 (Python)

🔷 백준 1759번 – 암호 만들기 (Python)

문제 설명

문제

암호는 서로 다른 L개의 알파벳 소문자로 구성됩니다.
반드시 최소 1개의 모음(`a`, `e`, `i`, `o`, `u`)이 포함되어야 합니다.
반드시 최소 2개의 자음이 포함되어야 합니다.
알파벳은 사전 순으로 정렬되어 있어야 합니다.

주어진 C개의 문자 중에서 위 조건을 만족하는 모든 암호를 출력하는 프로그램을 작성합니다.

입력

L C
C개의 알파벳 (공백 구분)

출력

조건을 만족하는 모든 암호 (한 줄에 하나씩)

테스트케이스

예제 입력

4 6
a t c i s w

예제 출력

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

구체적 설명

이 문제에서 주어진 문자를 이용하여 만들 수 있는 모든 길이 L의 조합을 찾아야 하며, 그 조합이 모음 1개 이상 + 자음 2개 이상 조건을 만족하면 출력합니다. 예를 들어,

`a c i s` → 모음(`a`,`i`) 2개, 자음(`c`,`s`) 2개 → 조건 만족 (출력)
`a c s w` → 모음 1개, 자음 3개 → 조건 만족 (출력)
`c s t w` → 모음 없음 → 조건 불만족 (미출력)

📌 아이디어

이 문제는 **깊이 우선 탐색(DFS)**과 **백트래킹**을 사용해 해결합니다. 핵심 아이디어는 주어진 `C`개의 문자 각각에 대해 '선택'할지 '선택하지 않을지'를 결정하며 가능한 모든 조합을 탐색하는 것입니다. DFS를 통해 모든 경우의 수를 탐색하며, 암호의 길이가 `L`이 되고 모음 1개 이상, 자음 2개 이상이라는 조건을 만족하면 해당 암호를 출력합니다. 또한, 알파벳은 사전 순으로 정렬되어 있어야 하므로, 입력 문자를 미리 정렬합니다.

전체 코드

def DFS(index:int):
    global cnt_mo
    global cnt_za
    global L
    global C

    # 1. 종료 조건 1: L개의 문자를 모두 선택한 경우
    if cnt_mo + cnt_za == L:
        if cnt_mo >= 1 and cnt_za >= 2: # 모음 1개 이상, 자음 2개 이상 조건 검사
            for i in range(C):
                if check[i] == 1: # 선택된 문자만 출력
                    print(arr[i], end='')
            print() # 줄 바꿈
        return

    # 2. 종료 조건 2: 모든 문자를 다 확인했지만 L개를 채우지 못한 경우
    if index >= C:
        return
    
    # 3. 현재 문자를 '선택'하는 경우
    check[index]=1 # 현재 문자 선택 표시
    if arr[index] in ['a','e','i','o','u']: # 모음인지 확인 후 개수 증가
        cnt_mo+=1
    else: # 자음이면 자음 개수 증가
        cnt_za+=1
    DFS(index+1) # 다음 문자로 재귀 호출

    # 4. 백트래킹: 현재 문자의 선택을 '해제'하고 이전 상태로 복원
    check[index]=0
    if arr[index] in ['a', 'e', 'i', 'o', 'u']: # 모음 개수 감소
        cnt_mo -= 1
    else: # 자음 개수 감소
        cnt_za -= 1
    
    # 5. 현재 문자를 '선택하지 않는' 경우
    DFS(index+1,)

# 전역 변수 초기화
cnt_mo=0
cnt_za=0

# 입력 받기
L, C = map(int,input().split())
arr = list(input().split())

# 선택 여부 배열 초기화
check = [0 for _ in range(C)]

# 암호가 사전 순으로 정렬되어야 하므로, 입력 문자들을 미리 정렬
arr.sort()

# DFS 탐색 시작
DFS(0)

백준 1759번 – 암호 만들기 (Python)

🔷 백준 1759번 – 암호 만들기 (Python)

문제 설명

문제

암호는 서로 다른 L개의 알파벳 소문자로 구성됩니다.
반드시 최소 1개의 모음(`a`, `e`, `i`, `o`, `u`)이 포함되어야 합니다.
반드시 최소 2개의 자음이 포함되어야 합니다.
알파벳은 사전 순으로 정렬되어 있어야 합니다.

주어진 C개의 문자 중에서 위 조건을 만족하는 모든 암호를 출력하는 프로그램을 작성합니다.

입력

L C
C개의 알파벳 (공백 구분)

출력

조건을 만족하는 모든 암호 (한 줄에 하나씩)

테스트케이스

예제 입력

4 6
a t c i s w

예제 출력

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

구체적 설명

`a c i s` → 모음(`a`,`i`) 2개, 자음(`c`,`s`) 2개 → 조건 만족 (출력)
`a c s w` → 모음 1개, 자음 3개 → 조건 만족 (출력)
`c s t w` → 모음 없음 → 조건 불만족 (미출력)

📌 아이디어

전체 코드

def DFS(index:int):
    global cnt_mo
    global cnt_za
    global L
    global C

    # 1. 종료 조건 1: L개의 문자를 모두 선택한 경우
    if cnt_mo + cnt_za == L:
        if cnt_mo >= 1 and cnt_za >= 2: # 모음 1개 이상, 자음 2개 이상 조건 검사
            for i in range(C):
                if check[i] == 1: # 선택된 문자만 출력
                    print(arr[i], end='')
            print() # 줄 바꿈
        return

    # 2. 종료 조건 2: 모든 문자를 다 확인했지만 L개를 채우지 못한 경우
    if index >= C:
        return
    
    # 3. 현재 문자를 '선택'하는 경우
    check[index]=1 # 현재 문자 선택 표시
    if arr[index] in ['a','e','i','o','u']: # 모음인지 확인 후 개수 증가
        cnt_mo+=1
    else: # 자음이면 자음 개수 증가
        cnt_za+=1
    DFS(index+1) # 다음 문자로 재귀 호출

    # 4. 백트래킹: 현재 문자의 선택을 '해제'하고 이전 상태로 복원
    check[index]=0
    if arr[index] in ['a', 'e', 'i', 'o', 'u']: # 모음 개수 감소
        cnt_mo -= 1
    else: # 자음 개수 감소
        cnt_za -= 1
    
    # 5. 현재 문자를 '선택하지 않는' 경우
    DFS(index+1,)

# 전역 변수 초기화
cnt_mo=0
cnt_za=0

# 입력 받기
L, C = map(int,input().split())
arr = list(input().split())

# 선택 여부 배열 초기화
check = [0 for _ in range(C)]

# 암호가 사전 순으로 정렬되어야 하므로, 입력 문자들을 미리 정렬
arr.sort()

# DFS 탐색 시작
DFS(0)

개별 코드 설명

1. 전역 변수 및 초기화

cnt_mo=0
cnt_za=0
L,C = map(int,input().split())
arr=list(input().split())
check=[0 for _ in range(C)]
arr.sort()

`cnt_mo`, `cnt_za`: 현재까지 선택된 모음과 자음의 개수를 추적하는 전역 변수입니다.
`L`, `C`: 각각 암호의 길이와 주어진 전체 문자의 개수를 입력받습니다.
`arr`: 입력된 `C`개의 문자들을 리스트로 저장합니다.
`check`: 각 문자가 현재 암호 조합에 선택되었는지(`1`) 또는 선택되지 않았는지(`0`)를 표시하는 리스트입니다. `C` 크기만큼 `0`으로 초기화됩니다.
`arr.sort()`: 문제 조건에 따라 알파벳은 사전 순으로 정렬되어야 하므로, DFS를 시작하기 전에 `arr` 리스트를 미리 정렬합니다. 이렇게 하면 DFS 탐색 과정에서 자연스럽게 사전 순의 조합이 생성됩니다.

2. DFS 재귀 함수 (`DFS(index: int)`)

def DFS(index:int):
    global cnt_mo
    global cnt_za
    global L
    global C
    # ... (코드 본문) ...

`global` 키워드를 사용하여 `cnt_mo`, `cnt_za`, `L`, `C` 변수를 함수 내에서 전역 변수로 접근하고 수정할 수 있도록 선언합니다.

3. 기저 조건 (종료 조건)

    if cnt_mo + cnt_za == L:
        if cnt_mo >= 1 and cnt_za >= 2:
            for i in range(C):
                if check[i] == 1:
                    print(arr[i], end='')
            print()
        return
    if index >= C:
        return

**첫 번째 종료 조건 (`cnt_mo + cnt_za == L`)**: 현재까지 선택된 문자의 총 개수가 `L`과 같아지면, 암호 길이가 `L`에 도달했음을 의미합니다.
- 이때, **모음이 1개 이상**(`cnt_mo >= 1`)이고 **자음이 2개 이상**(`cnt_za >= 2`)인지 조건을 확인합니다.
- 두 조건을 모두 만족하면, `check` 리스트를 순회하며 `1`로 표시된 문자들(`arr[i]`)을 연결하여 출력하고 줄 바꿈합니다.
- 조건 만족 여부와 관계없이 암호 길이에 도달했으므로 `return`하여 현재 재귀 호출을 종료하고 이전 단계로 돌아갑니다.
**두 번째 종료 조건 (`index >= C`)**: `index`가 `C`에 도달하거나 초과하면, 이는 주어진 모든 문자(`arr`)에 대해 선택/비선택 결정을 완료했음을 의미합니다. 더 이상 탐색할 문자가 없으므로 `return`하여 재귀 호출을 종료합니다.

4. 선택 / 비선택 분기 (백트래킹)

    else:
        # 현재 문자를 '선택'하는 경우
        check[index]=1
        if arr[index] in ['a','e','i','o','u']:
            cnt_mo+=1
        else:
            cnt_za+=1
        DFS(index+1)

        # 백트래킹: 현재 문자의 선택을 '해제'하고 이전 상태로 복원
        check[index]=0
        if arr[index] in ['a', 'e', 'i', 'o', 'u']:
            cnt_mo -= 1
        else:
            cnt_za -= 1
        
        # 현재 문자를 '선택하지 않는' 경우
        DFS(index+1,)

`else` 블록은 기저 조건에 해당하지 않을 때 실행됩니다. 이는 아직 모든 문자를 확인하지 않았음을 의미합니다.
**현재 문자 `arr[index]`를 `선택`하는 경우:**
- `check[index]`를 `1`로 설정하여 현재 문자를 암호에 포함시킵니다.
- `arr[index]`가 모음인지 자음인지 판별하여 해당 카운터(`cnt_mo` 또는 `cnt_za`)를 1 증가시킵니다.
- `DFS(index + 1)`을 호출하여 다음 문자에 대한 선택/비선택 결정을 재귀적으로 이어갑니다.
**백트래킹**: `DFS(index + 1)` 호출이 완료되어 이 지점으로 돌아오면, 현재 `arr[index]` 문자의 선택을 '해제'합니다.
- `check[index]`를 `0`으로 다시 설정하고, 이전에 증가시켰던 `cnt_mo` 또는 `cnt_za`를 1 감소시켜 상태를 되돌립니다. 이 과정은 다음 경우의 수를 탐색하기 위한 필수적인 단계입니다.
**현재 문자 `arr[index]`를 `선택하지 않는` 경우:**
- 백트래킹 이후, `DFS(index + 1)`을 다시 호출하여 현재 문자를 포함하지 않은 상태에서 다음 문자로 넘어가는 경우를 탐색합니다.

결론

이 문제는 **조합(Combination)** 문제입니다. 주어진 문자들 중에서 `L`개의 문자를 선택하는 모든 조합을 고려합니다.
**DFS(깊이 우선 탐색)**를 이용하여 각 문자를 선택하거나 선택하지 않는 두 가지 경우를 재귀적으로 탐색함으로써 가능한 모든 조합을 빠짐없이 확인합니다.
**백트래킹**을 통해 재귀 호출이 끝난 후 상태를 이전으로 되돌려 다른 경우의 수를 탐색할 수 있도록 합니다.
**모음 1개 이상, 자음 2개 이상**이라는 암호 조건을 만족하는 조합만을 출력하며, 사전에 문자들을 정렬하여 출력 순서도 자동으로 맞춥니다.
주어진 `C`의 최대값(15)을 고려할 때, 모든 조합을 탐색하는 방식(2^15 = 32,768가지)은 시간 복잡도 면에서 충분히 허용 가능합니다.

'백준 스터디' 카테고리의 다른 글

백준 12852번 '1로 만들기 2' Python (4)	2025.08.01
백준 12852번 1로 만들기 2 C++ (0)	2025.08.01
백준 1759번 암호 만들기 C++ (2)	2025.07.31
백준 11053번 – 가장 긴 증가하는 부분 수열 (Python) (2)	2025.07.31
백준 11053번 – 가장 긴 증가하는 부분 수열 (C++) (1)	2025.07.31

공지사항

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

링크

TAG more

« 2025/09 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

글 보관함

프로그래밍 및 개발 공부하기

티스토리 뷰