Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
Tags
- 컴퓨터공학 #c #c언어 #문자열입력
- 잔
- HTML #CSS
- 컴퓨터공학 #Java #자바 #클래스 #객체 #인스턴스
- 컴퓨터공학 #자료구조 #스택 #c++ #알고리즘 #백준문제풀이
- BOJ #컴퓨터공학 #C++ #알고리즘 #자료구조
Archives
- Today
- Total
영벨롭 개발 일지
[백준 BOJ][C++]1759번 암호 만들기 풀이: DFS 본문
https://www.acmicpc.net/problem/1759
이 문제는 DFS로 해결할 수 있습니다.
[풀이 과정]
1. L과 C 입력
2. C개의 알파벳 입력하고 num에 저장
3. num을 오름차순으로 정렬
4. 모든 원소에 대해 순차적으로 dfs 실행
5. 현재 알파벳보다 다음에 위치한 알파벳에 대해 아직 방문 여부 체크
6. 아직 방문하지 않았다면 방문 표시 후, arr[depth]=다음 알파벳, 자음인지 모음인지 체크 후 dfs 호출후 방문 표시 해제
7. depth가 L이고 자음이 2개 이상, 모음이 1개 이상이라면 arr의 모든 원소 출력
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int L, C;
char alphabet[16];
char arr[16];
bool visit[16] = { false, };
bool is_consonant(char c) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
return false;
return true;
}
void dfs(int idx, int c, int v, int depth) {
if (depth == L && c > 1 && v > 0) {
for (int i = 0; i < L; i++)
cout << arr[i];
cout << endl;
return;
}
else if (depth == L && (c < 2 || v < 1))
return;
for (int i = idx + 1; i < C; i++) {
if (!visit[i]) {
visit[i] = true;
char ch = alphabet[i];
arr[depth] = ch;
if (is_consonant(ch))
dfs(i, c + 1, v, depth + 1);
else
dfs(i, c, v + 1, depth + 1);
visit[i] = false;
}
}
}
int main(void) {
cin >> L >> C;
for (int i = 0; i < C; i++) {
cin >> alphabet[i];
}
sort(alphabet, alphabet + C);
for (int i = 0; i < C; i++) {
memset(visit, false, sizeof(visit));
arr[0] = alphabet[i];
visit[i] = true;
int c = 0;
int v = 0;
if (is_consonant(alphabet[i])) {
c++;
}
else {
v++;
}
dfs(i, c, v, 1);
}
return 0;
}
반응형
'알고리즘 문제 풀이 > BOJ' 카테고리의 다른 글
[백준 BOJ][C++]2529번 부등호 풀이: DFS (0) | 2022.04.08 |
---|---|
[백준 BOJ][C++]14501번 퇴사 풀이: 브루트 포스 & 재귀 (0) | 2022.04.08 |
[백준 BOJ][C++]2210번 숫자판 점프 풀이: DFS (0) | 2022.04.06 |
[백준 BOJ][C++]14889번 스타트와 링크 풀이: DFS (0) | 2022.04.05 |
[백준 BOJ][C++]6603번 로또 풀이: DFS (0) | 2022.04.05 |