경우없는 개발 블로그

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

#문제 간단 정리

이 문제는 동시에 빙고가 나오는지 확인을 하면 되는데

빙고는 행 빙고만 취급한다.

#문제 해결 방법

만약 두 빙고카드에 같은 행에

같은 숫자가 존재한다면 

비길 수 있는 가능성으로 만드는 가능성이 존재한다.

하지만 만약

1 2 3 4 5

1 6 7 8 9

2 3 4 6 7

1 2 3 4 5

에서 1을 찾고

1 6 7 8 9 

에서 1을 찾아서

비긴다고 생각을해도

나머지 2 3 4 5, 6 7 8 9

을 빙고하다보면

2 3 4 6 7 행이 빙고가 되서 비기지 않는다

즉 다른카드에서 겹치는 쌍을 찾고

1 2 3 4 5 에서 1을 골랏다면 2 3 4 5 를 추출

1 6 7 8 9 에서 1을 골랏다면 6 7 8 9 를 추출해서

2 3 4 5 6 7 8 9 로 이루어진 빙고가 없는지 조사해야된다.

#전체 코드

#include <iostream>
#include <vector>
#include <set>

using namespace std;

vector<vector<vector<int>>> numbers;
int n;

//각 행이 나머지 숫자들로 빙고가 되는지 학인하기 , 빙고가 안된다면 false 된다면 true
bool remainMatch(vector<int>& remainOne, vector<int>& remainTwo, int dupi1, int dupj1, int dupi2, int dupj2) {

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < 5; j++) {
            //같은세트의 같은 행은 조사하지 않음
            if (i != dupi1 || j != dupj1) {
 
                if (i != dupi2 || j != dupj2) {


                    vector<bool> check(5, false);

                    for (int k = 0; k < 5; k++) {

                        for (auto a : remainOne) {
                            if (numbers[i][j][k] == a) {
                                check[k] = true;

                            }
                        }
                        for (auto a : remainTwo) {
                            if (numbers[i][j][k] == a) {
                                check[k] = true;
                            }
                        }

                    }

                    bool allCheck = true;
                    for (auto a : check) {
                        if (!a) {
                            allCheck = false;
                        }
                    }
                    //전부 true 면 false 반환

                    if (allCheck) {

                        return true;
                    }

                }
            }

        }


    }

    return false;
}

int main() {

    cin >> n;

    for (int i = 0; i < n; i++) {
        vector<vector<int>> temp(5, vector<int>(5));
        for (int u = 0; u < 5; u++) {
            for (int j = 0; j < 5; j++) {
                cin >> temp[u][j];
            }
        }

        numbers.push_back(temp);
    }

    //일치되는 숫자를 찾고 , 일치되는 숫자 쌍의 행에서 나머지를 추출해서 그 나머지들로 이뤄지는 빙고가 있는지 확인
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < 5; k++) {
            for (int t = 0; t < 5; t++) {
                int target = numbers[i][k][t];

                vector<int> remainOne;

                for (int b = 0; b < 5; b++) {
                    if (b == t) continue;
                    //추출한 첫번쨰 숫자의 나머지 행의 원소들 저장
                    remainOne.push_back(numbers[i][k][b]);
                }

                //다음 빙고셋트들 확인
                for (int j = i + 1; j < n; j++) {

                    for (int p = 0; p < 5; p++) {
                        for (int l = 0; l < 5; l++) {
                            if (target == numbers[j][p][l]) { //같으면 나머지 챙겨서 확인

                                vector<int> remainTwo;

                                for (int b = 0; b < 5; b++) {
                                    if (b == l) continue;
                                    //일치한 두번째 숫자의 나머지 행의 원소들 저장
                                    remainTwo.push_back(numbers[j][p][b]);
                                }


                                if (!remainMatch(remainOne, remainTwo, i, k, j, p)) {
                                    cout << i + 1 << ' ' << j + 1 << '\n';
                                    return 0;
                                }


                            }
                        }
                    }

                }

            }
        }
    }

    cout << "no ties" << '\n';
    return 0;
}

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

#문제 간단 정리

#문제 해결 방법

    // dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수
    // 1. j를 포함하지 않고 만드는경우
    // dp[i][j-1];
    // 2. j를 포함해서 i를 만드는경우
    // if(i>=j)  D[i][j] = (D[i][j] + D[i-j][j-1]) % mod ; 
    // D[i-j][j-1] = i-j를 1 ~ j-1 사이의 수들로 만드는방법의 수 

일단 해결로직은 저렇긴한데

dp를 떠올리는 발상을 정리해보자면 

일단 특정 숫자를 쓰냐 안쓰냐로 생각 할 수 있고

j를 안쓰고 만들면 j-1 개를 가지고 만드는 가지수와 같고

j까지의 숫자를 써서 N을 만드는 방법은 = j-1 까지의 숫자를  써서 N-j 을 만들는 방법 + j를 안쓰고 만드는 방법으로 나눌수 있다

때문에 i 를 j 개의 숫자를 써서 만드는

dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수 를 떠올리면 된다

#전체 코드

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
#define MOD 100999

int dp[2001][2001];

int main() {

    int t;
    int n;

    // dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수
    // 1. j를 포함하지 않고 만드는경우
    // dp[i][j-1];
    // 2. j를 포함해서 i를 만드는경우
    // if(i>=j)  D[i][j] = (D[i][j] + D[i-j][j-1]) % mod ; 
    // D[i-j][j-1] = i-j를 1 ~ j-1 사이의 수들로 만드는방법의 수 


    dp[0][0] = 1;
    for (int i = 1; i < 2001; i++) {
        dp[i][0] = 0;
        dp[0][i] = 1;
    }
    for (int i = 1; i < 2001; i++) {
        for (int j = 1; j < 2001; j++) {
            dp[i][j] = dp[i][j - 1];  //j를 포함하지 않고 i를 만드는 경우
            if (i >= j) {
                dp[i][j] += dp[i - j][j - 1];
                dp[i][j] %= MOD;
            }
        }
    }

    cin >> t;
    while (t--) {
        cin >> n;
        cout << dp[n][n] << endl;
    }


    return 0;
}

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

#문제 간단 정리

#문제 해결 방법

맵을 쓰는 간단한 문제

eof와 

자리수 출력에 주의하자

#전체 코드

#include <iostream>
#include <map>
#include <string>
#include <iomanip>

using namespace std;

int main() {
    map<string, int> trees;
    int total = 0;
    string tree;

    while (getline(cin, tree)) {
        trees[tree]++;
        total++;
    }


    cout << fixed << setprecision(4);
    for (auto& entry : trees) {
        double percentage = (entry.second * 100.0) / total;
        cout << entry.first << " " << percentage << '\n';
    }

    return 0;
}

#동적 계획법(DP)이란?

DP의 두 가지 핵심 특성

1. 중복되는 부분 문제(Overlapping Subproblems):
   • 동적 계획법은 문제를 풀 때 동일한 부분 문제가 여러 번 반복됩니다. 예를 들어, 피보나치 수열에서 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)를 구할 때, F(n−1)F(n-1)F(n−1)과 F(n−2)F(n-2)F(n−2)을 재귀적으로 구하게 됩니다. 하지만 F(n−2)F(n-2)F(n−2)는 F(n−1)F(n-1)F(n−1)을 계산할 때도 다시 구하게 됩니다. 이처럼 중복된 계산이 자주 발생하므로, 이를 메모이제이션 또는 테이블 저장을 통해 중복 계산을 방지합니다.
2. 최적 부분 구조(Optimal Substructure):
   • 최적 부분 구조란, 큰 문제의 해답이 그 문제를 구성하는 작은 문제들의 최적 해답으로부터 도출될 수 있다는 특성입니다. 즉, 작은 문제의 최적 해가 변하지 않고 그대로 전체 문제의 최적 해를 이루는 데 기여한다는 것입니다.
   • 예를 들어, 피보나치 수열에서 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)로 계산할 수 있듯이, 작은 문제들의 최적해를 통해 큰 문제의 답을 구할 수 있습니다.

동적 계획법의 활용 예

• 피보나치 수열: 피보나치 수열을 재귀적으로 구할 때, 각 숫자의 결과를 저장하여 중복된 계산을 방지합니다.
• 배낭 문제: 배낭 문제에서 최대 가치를 구할 때, 각 부분 문제(작은 용량의 배낭에서 최대 가치를 구하는 문제)가 전체 문제의 해답을 구성합니다.

즉 DP 는 동일한 부분문제가 반복되면서 그 부분문제로 전체의 큰 문제를 풀 수 있으며

작은 문제의 최적 해가 바뀌지 않을 때 라고 할 수 있다.

#분할 정복(Divide and Conquer)이란?

**분할 정복(Divide and Conquer)**은 문제를 더 작은 부분 문제로 나눈 후, 각 부분 문제를 독립적으로 해결하고, 이들의 해답을 합쳐서 전체 문제를 해결하는 방식입니다. 분할 정복에서는 중복된 부분 문제가 발생하지 않으며, 각 부분 문제의 결과가 전체 문제의 최적 해답을 직접적으로 보장하지는 않습니다.

분할 정복의 특징

1. 최적 부분 구조가 없다:
   • 분할 정복에서는 각 부분 문제의 해답이 전체 문제의 최적 해답을 바로 보장하지 않습니다. 작은 문제들을 해결한 후, 이를 병합하는 과정에서 전체 문제의 해답이 달라질 수 있습니다.
   • 예를 들어, 병합 정렬(Merge Sort)에서 부분 배열이 정렬되었다고 해서 바로 전체 배열이 정렬되는 것은 아닙니다. 부분 배열들을 병합해야 최종적으로 전체 배열이 정렬됩니다.
2. 중복되는 부분 문제가 없다:
   • 분할 정복에서 각 부분 문제는 독립적입니다. 동일한 부분 문제가 여러 번 반복되지 않으며, 한 번 계산한 부분 문제는 다른 문제에서 다시 계산되지 않습니다.
   • 이는 동적 계획법과의 큰 차이점 중 하나입니다. 예를 들어, 병합 정렬에서 배열을 두 부분으로 나누어 정렬할 때, 같은 부분 문제를 반복해서 계산하지 않으며, 각 부분 문제는 독립적으로 처리됩니다.

분할 정복의 활용 예

• 병합 정렬(Merge Sort): 배열을 반으로 나누어 각각을 정렬한 후, 두 정렬된 배열을 병합하여 전체 배열을 정렬하는 알고리즘입니다. 작은 문제들이 해결된 후에도 병합 과정에서 전체 해답이 결정됩니다.
• 퀵 정렬(Quick Sort): 피벗을 기준으로 배열을 나누어 각각을 정렬하고, 그 결과를 합쳐서 전체 배열을 정렬하는 알고리즘입니다.

동적 계획법 (DP)                                                                               분할 정복 (Divide and Conquer)

# 쉽게 생각해서..

예를들어서 병합정렬을 생각해보도록하자

병합정렬은 부분으로 나눠서 정렬하는데

결국에는 합쳐서 모두 정렬을 해야 되기 때문에

부분적으로 정렬한것이 그대로 최적해가 보장되지 않는다고 할 수 있다.

(부분 정렬한거 그대로 사용 안하니까)

때문에  부분 문제의 답이 최적해가 아니라고 볼 수 있고

그리고 또한

**병합 정렬(Merge Sort)**에서는 부분 배열을 계속해서 더 작은 부분으로 나눠도, 이미 처리된 부분 문제를 다시 처리하지 않는다. 이게 바로 중복되는 부분 문제가 없다는 의미이다

더 설명해보자면

병합정렬을 위해서 부분을 쪼개서 합치게 된다면

그 합쳐진 부분문제는 "다른문제" 라고 할 수 있다.

왜냐면 그 다른 문제를 풀때는 이전의 부분문제를 요구하지 않기 때문이다.

 때문에 이전문제를 메모리제이션 할 필요가 없으니 중복되는 부분문제라 볼수 없다

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

#문제 간단 정리

#문제 해결 방법

우선 동적 계획법을 사용해야된다는건 쉽게 알아차릴 수 있다

왜냐면 

1. 중복되는 부분 문제(Overlapping Subproblems)

2. 최적 부분 구조(Optimal Substructure)

를 n의 조합을 알기 위해서는 이전의 수가 필요하고 이전의 수 조합으로 구할 수 있다는 것을 쉽게 알 수 있기 때문이다.

그렇다면 선택할수 있는건 

그 수의 조합을 만들기 위해 어떤수를 사용하던가 사용하지 않던가 

로 나뉜다는 것을 알 수 있다.

   // dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수
    // 1. j를 포함하지 않고 만드는경우
    // dp[i][j-1];
    // 2. j를 포함해서 i를 만드는경우
    // if(i>=j)  D[i][j] = (D[i][j] + D[i-j][j-1]) % mod ; 
    // D[i-j][j-1] = i-j를 1 ~ j-1 사이의 수들로 만드는방법의 수 

#전체 코드

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
#define MOD 100999

int dp[2001][2001];

int main() {

    int t;
    int n;

    // dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수
    // 1. j를 포함하지 않고 만드는경우
    // dp[i][j-1];
    // 2. j를 포함해서 i를 만드는경우
    // if(i>=j)  D[i][j] = (D[i][j] + D[i-j][j-1]) % mod ; 
    // D[i-j][j-1] = i-j를 1 ~ j-1 사이의 수들로 만드는방법의 수 


    dp[0][0] = 1;
    for (int i = 1; i < 2001; i++) {
        dp[i][0] = 0;
        dp[0][i] = 1;
    }
    for (int i = 1; i < 2001; i++) {
        for (int j = 1; j < 2001; j++) {
            dp[i][j] = dp[i][j - 1];  //j를 포함하지 않고 i를 만드는 경우
            if (i >= j) {
                dp[i][j] += dp[i - j][j - 1];
                dp[i][j] %= MOD;
            }
        }
    }

    cin >> t;
    while (t--) {
        cin >> n;
        cout << dp[n][n] << endl;
    }


    return 0;
}

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

#문제 간단 정리

기본적인 bfs 구현문제

#문제 해결 방법

bfs 를 조회할때 

색약인지 색약인지 아닌지를 구분받아서 조회할 수 있는지 

물어보는 문제이다

색약인경우의 조건을 잘 구현하자

#전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int dy[4] = { 0,-1,0,1 };
int dx[4] = { -1,0,1,0 };

int n;
vector<vector<char>> rgb;
vector<vector<bool>> check;
int blindCount;
int nBlindCount;

void bfs(int y, int x, bool blind) {

    queue<pair<int, int>> q;
    q.push({ y,x });
    check[y][x] = true;

    char color = rgb[y][x];


    while (!q.empty() && !blind) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (0<=nx && nx <n && 0<= ny && ny<n ) {

                if (check[ny][nx] == false) {
                    if (rgb[ny][nx] == color) {
                        q.push({ ny, nx });

                        check[ny][nx] = true;
                    }
                }


            }

        }

    }

    while (!q.empty() && blind) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < n) {

                if (check[ny][nx] == false) {
                    if (color == 'B' && rgb[ny][nx] == color) {
                        q.push({ ny, nx });

                        check[ny][nx] = true;
                    }
                    else if (color == 'R' || color == 'G') {
                        if (rgb[ny][nx] == 'R' || rgb[ny][nx] == 'G') {
                            q.push({ ny, nx });

                            check[ny][nx] = true;
                        }

                    }
                }



            }

        }

    }


}

int main() {
    cin >> n;

    rgb.resize(n, vector<char>(n));
    check.resize(n, vector<bool>(n, false));

    for (int i = 0; i < n; i++) {
        string s; cin >> s;

        for (int j = 0; j < n; j++) {
            rgb[i][j] = s[j];

        }

    }

    blindCount = 0;
    nBlindCount = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j] == false) {
                bfs(i, j, false);
                nBlindCount++;
            }

        }
    }

    check.assign(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j] == false) {
                bfs(i, j, true);
                blindCount++;
            }


            
        }
    }

    cout << nBlindCount << ' ' << blindCount << '\n';

    return 0;
}

A. Sakurako's Exam

a b 가 주어지는데 a개수만큼 1이 주어지고 b의 개수만큼 2가 주어지는데

각 숫자 사이에 부호를 + , -를 배치해서 0을 만들수 있는지 출력하는문제

a와 b의 개수를 파악해서 각자 짝수냐 홀수냐 그리고 1의개수를 잘 따지면 된다

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
 
int main() {
    
    int t;
    cin >> t;
 
    while (t--) {
        int a, b;
        cin >> a >> b;
 
        int remainB = 0;
        if (b % 2 != 0) {
            remainB = b % 2;
        }
 
        if (a  == remainB *2) {
            cout << "yes" << '\n';
        }
        else if (a % 2 != 0 || a == 0) {
            cout << "no" << '\n';
        }
        else {
            cout << "yes" << '\n';
        }
 
    }
 
    return 0;
}

B. Square or Not

정사각형의 테두리는 1이고 가운데는 0인 행렬로 만들 수 있는지 물어보는 문제

주어지는 입력이 한줄로 이뤄지기 때문에

이 한줄 입력을 정사각행렬에 맞춰서 인덱스 조회가 가능한지 물어보는 문제

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
 
 
int main() {
    
    int t;
    cin >> t;
 
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
 
        bool flag = true;
 
        int root = sqrt(n);
        if (root * root != n) {
            flag = false;
        }
 
        for (int i = 0; i < root; i++) {
            if (s[i] != '1' || s[n - root + i] != '1') flag = false;
 
            if (s[i * root] != '1' || s[(i + 1) * root - 1] != '1') flag = false;
        }
 
        for (int i = 1; i < root - 1; i++) {
            for (int j = 1; j < root - 1; j++) {
                if (s[i * root + j] != '0') flag = false;
            }
        }
 
        if (flag) {
            cout << "yes" << '\n';
        }
        else {
            cout << "no" << '\n';
        }
    }
 
    return 0;
}

C. Longest Good Array

점점 증가하는 행렬을 만드는데 이전과 원소와의 차이도 증가하는 행렬을 만드는 문제

차이가 점점 증가하므로 등차수열을 활용하면 된다 

#include <iostream>
using namespace std;
 
 
long long sum_sequence(long long n) {
    return n * (n + 1) / 2;
}
 
int longest_array(int l, int r) {
    int diff = r - l;
 
 
    int left = 0, right = 10000000; 
    int max_n = 0;
 
    while (left <= right) {
        int mid = (left + right) / 2;
        if (sum_sequence(mid) <= diff) {
            max_n = mid; 
            left = mid + 1;
        }
        else {
            right = mid - 1; 
        }
    }
 
    return max_n + 1; 
}
 
int main() {
    int t;
    cin >> t; 
 
    while (t--) {
        int l, r;
        cin >> l >> r; 
 
 
        if (l == r) {
            cout << 1 << endl;
        }
        else {
            cout << longest_array(l, r) << endl;
        }
    }
 
    return 0;
}

D. Sakurako's Hobby

각 배열을 흰색 혹은 블랙으로 이뤄져있고

각 배열의 인덱스 i 에서 배열의 원소가 3이라면 3의 인덱스를 참조하고 배열의 인덱스 3 의 p[3] 원소를 또참조해서 만나는 블랙의 원소들의 개수를 전부 카운팅 하는 문제

말그대로 구현문제이다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
 
 
int main() {
    int t;
    cin >> t;
 
    while (t--) {
        int n;
        cin >> n;
 
        vector<int> p(n);
        vector<int> F(n, -1);
        vector<bool> visited(n, false);
 
        for (int i = 0; i < n; i++) {
            cin >> p[i];
            p[i]--;
        }
 
        string s;
        cin >> s;
 
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
 
            vector<int> cycle;
            int x = i;
            while (!visited[x]) {
                visited[x] = true;
                cycle.push_back(x);
                x = p[x]; 
            }
 
 
            int black_count = 0;
            for (int idx : cycle) {
                if (s[idx] == '0') black_count++;
            }
 
            for (int idx : cycle) {
                F[idx] = black_count;
            }
        }
 
        for (int i = 0; i < n; i++) {
            cout << F[i] << " ";
        }
        cout << endl;
    }
 
    return 0;
}

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

#문제 간단 정리

bfs를 통한 거리 문제

#문제 해결 방법

이 문제는 bfs를 통해서

가장 먼 거리의 위치 를 찾는 문제이다

전형적이 bfs에서 조금 활용이라고 볼 수 있다.

모든 육지 노드에 대해 돌면서 그 육지에서

가장 먼 노드를 찾고

가장 먼 거리를 변수에 저장하면 된다.

#전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n, m;

int dy[4] = { 0,1,0,-1 };
int dx[4] = { -1,0,1,0 };
vector<vector<char>> tMap;
int maxDist;

int bfs(int inputY, int inputX) {
    //좌표,거리
    queue<pair<int, int>> q;
    vector<vector<int>> dist(n, vector<int>(m, -1));

    q.push({ inputY,inputX });
    dist[inputY][inputX] = 0;
    int mdist = 0;

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < m && 0 <= ny && ny < n) {
                if (tMap[ny][nx] == 'L') {
                    if (dist[ny][nx] == -1 || dist[ny][nx] > dist[y][x] + 1) {
                        q.push({ ny,nx });
                        dist[ny][nx] = dist[y][x] + 1;
                    }
                }
            }
        }

    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            mdist = max(mdist, dist[i][j]);
        }
    }

 /*   for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }

    cout << '\n';*/
    return mdist;
}

int main()
{

    cin >> n >> m;

    tMap.resize(n, vector<char>(m));
    maxDist = 0;

    for (int i = 0; i < n; i++) {
        string input;
        cin >> input;

        for (int j = 0; j < m; j++) {
            tMap[i][j] = input[j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tMap[i][j] == 'L') {
                maxDist = max(bfs(i, j), maxDist);
            }
        }
    }

    cout << maxDist << '\n';

}

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

#문제 간단 정리

그래프 탐색을 하면 된다

#문제 해결 방법

dfs로 풀었는데

트리의 부모만 확인해 주면 되니까 이렇게 복잡하게 풀 필요는 없어보인다..

그래서 실버1인듯하다

#전체 코드

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <climits>

using namespace std;

map<string, vector<string>> node;
map<string, bool> dfsCheck;
int result;

void dfs(string start, string target) {

    if (start == target) {
        result = 1;
        return;
    }



    for (auto a : node[start]) {
        if (!dfsCheck[a]) {
            dfsCheck[start] = true;
            dfs(a, target);
            dfsCheck[start] = false;
        }
    }

    
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n - 1; i++) {
        string s1, s2;
        cin >> s1 >> s2;

        dfsCheck[s1] = false;
        dfsCheck[s2] = false;

        node[s1].push_back(s2);
    }

    string a1, a2;
    cin >> a1 >> a2;
    result = 0;

    dfs(a1, a2);
    dfs(a2, a1);
    
    cout << result << '\n';

    return 0;
}

#문제상황

우선 

지금은 제대로 정렬 되어 있지만 

이상하게 서버에 올려서 이름순 정렬을 하면 제대로 되지 않는 문제가 있었습니다.

서버는 PostgreSql 로컬은 H2를 사용해서 돌아가게 되어있습니다.

#해결방법

PostgreSQL을 사용하여 데이터를 정렬할 때, 한글이 포함된 컬럼의 정렬이 예상과 다르게 동작하는 경우가 발생할 수 있습니다. 예를 들어, ORDER BY 구문을 사용하여 한글이 포함된 컬럼을 정렬할 때, 한글이 정상적으로 "가나다" 순으로 정렬되지 않고 엉뚱한 순서로 나오는 상황을 겪을 수 있습니다.

이 문제의 원인은 데이터베이스가 한글 정렬에 적합한 collation 설정을 사용하지 않았기 때문입니다.

Collation이란?

Collation은 데이터베이스에서 문자열을 비교하고 정렬할 때 사용하는 규칙을 정의하는 설정입니다. PostgreSQL에서는 데이터베이스를 생성할 때 collation 설정을 지정할 수 있습니다. 기본적으로 en_US.UTF-8과 같은 영어 기반의 collation이 설정되어 있는 경우, 한글 정렬이 제대로 되지 않는 문제가 발생할 수 있습니다.

문제 원인 분석

PostgreSQL에서 데이터베이스의 collation이 한글 정렬에 적합하지 않은 값으로 설정된 경우, 한글이 올바르게 정렬되지 않습니다. 예를 들어, en_US.UTF-8로 설정된 데이터베이스는 한글을 영어 알파벳과 동일한 기준으로 정렬하기 때문에, 우리가 기대하는 "가나다" 순으로 정렬되지 않습니다.

이 문제를 해결하려면 데이터베이스를 생성할 때 올바른 collation을 설정해야 합니다.

해결 방법

1. 데이터베이스 생성 시 collation 설정하기

PgAdmin에서 생성시 Character type 을 C로 해준다

또는

데이터베이스를 처음 생성할 때 collation을 ko_KR.UTF-8로 설정하면 한글이 올바르게 정렬됩니다. 이 방법은 데이터베이스를 처음부터 설정하는 경우에 적합합니다.

CREATE DATABASE mydb
WITH ENCODING='UTF8'
LC_COLLATE='ko_KR.UTF-8'
LC_CTYPE='ko_KR.UTF-8'
TEMPLATE=template0;​

2. 이미 생성된 데이터베이스에서 collation 변경하기

이미 데이터베이스가 생성된 후에는 collation을 변경하기가 어렵습니다. 이 경우, 데이터베이스를 백업하고 새로운 collation 설정으로 데이터베이스를 다시 생성해야 합니다.

UPDATE PG_DATABASE SET DATCOLLATE = 'ko_KR.utf8',
WHERE DATNAME='[데이터베이스명]';

3. 쿼리 수준에서 collate 옵션 사용하기

만약 데이터베이스 전체를 재설정할 수 없는 상황이라면, 개별 쿼리에서 collate 옵션을 사용하는 방법도 있습니다. 이 방법은 쿼리마다 collation을 지정하여 한글이 올바르게 정렬되도록 합니다.

SELECT * FROM store
ORDER BY store_nm COLLATE "ko_KR.utf8";​

이 방법을 사용하면, 데이터베이스의 기본 collation을 변경하지 않고도 한글 정렬 문제를 해결할 수 있습니다.

참고 

https://jupiny.com/2016/12/12/sort-korean-in-postgresql/

https://gaagaagaa.tistory.com/entry/PostgreSQL-%ED%95%9C%EA%B8%80-%EC%A0%95%EB%A0%AC%EC%9D%B4-%EC%95%88%EB%90%A0-%EB%95%8Ccollate

https://uiandwe.tistory.com/1380