반응형

https://www.acmicpc.net/problem/12919

 

12919번: A와 B 2

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. unordered_map을 활용하여 문자열의 방문 여부를 저장합니다.

 

2. T문자열부터 시작하여 맨 뒤 문자가 'A'일 때와 맨 앞 문자가 'B'일 때 두 상황에서 각각 처리한 뒤 queue에 넣어주면서 S문자열과 같아지면 1을 출력하고 프로그램을 종료시킵니다.

 

3.  S문자열을 만들 수 없다면 0을 출력합니다.

 

[ 소스코드 ]

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<string>
#include<queue>
#include<unordered_map>
 
using namespace std;
 
string S, T;
unordered_map<string, int> visited;
 
string change(string S)
{
    string temp;
 
    for (int i = S.size()-1; i >= 0; i--) {
        temp += S[i];
    }
 
    return temp;
}
 
int main()
{
    cin >> S >> T;
 
    queue<string> q;
 
    q.push(T);
    visited[T] = 1;
 
    while (!q.empty()) {
        string A = q.front();
        q.pop();
 
        if (A == S) {
            printf("1");
            return 0;
        }
        if (A.size() == S.size()) continue;
 
        string temp = A;
        if (temp[temp.size() - 1] == 'A') {
            temp.erase(temp.end() - 1);
            if (visited[temp] != 1) {
                visited[temp] = 1;
                q.push(temp);
            }
        }
 
        temp = A;
 
        if (temp[0] == 'B') {
            temp = change(temp);
            temp.erase(temp.end() - 1);
            if (visited[temp] != 1) {
                visited[temp] = 1;
                q.push(temp);
            }
        }
    }
 
    printf("0");
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 7490번 - 0 만들기 (C++)  (0) 2023.06.14
[ 백준 ] 20437번 - 문자열 게임 2 (C++)  (0) 2023.06.13
[ 백준 ] 14463번 - 소가 길을 건너간 이유 9 (C++)  (0) 2023.06.11
[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)  (0) 2023.06.10
[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09

+ Recent posts

티스토리툴바