[ 프로그래머스 스킬트리 (Lv2) ] (C++)

프로그래머스의 스킬트리(Lv2) 문제이다.

 

[ 문제풀이 ]

스킬을 배우기 위한 스킬들의 순서가 주어졌을 때, 스킬트리로 가능한지를 판단해야 하는 문제이다.

문제에 대한 전체적인 접근 방법부터 구체적인 풀이과정까지 알아보도록 하자.

 

#1. 접근방법

스킬은 배워야 하는 순서가 정해져있다. 예시를 한가지 들어보자.

선행 스킬 순서가 "ABC" 라는 예시를 생각해보자.

스킬 'A' 를 보면, 이 전에 배워야 하는 스킬이 없어도 배울 수가 있는 스킬이다.

스킬 'B'를 보면, 이 전에 'A'라는 스킬을 반드시 배워야만 배울 수가 있는 스킬이다.

스킬 'C'를 보면, 이 전에 'A'와 'B' 스킬을 반드시 배워야만 배울 수가 있는 스킬이다.

그럼, 여기서 "선행으로 배워야 하는 스킬의 갯수" 의 관점에서 접근해보자.

 

스킬 'A'는 선행으로 배워야 하는 스킬의 갯수가 0개이다.

스킬 'B'는 선행으로 배워야 하는 스킬의 갯수가 1개이다. (A를 배운 후에야 배울 수 있으므로)

스킬 'C'는 선행으로 배워야 하는 스킬의 갯수가 2개이다. (A와 B를 배운 후에야 배울 수 있으므로)

 

즉 ! 스킬을 배우기 위해서는, 선행으로 배워야 하는 스킬의 갯수가 0개일 때만 올바르게 배울 수 있다.

위의 예시에서 'A'를 배웠다고 가정해보자. A를 배웠다면 ? 'B'는 선행으로 배워야 하는 스킬의 갯수가 0개가 된다. 왜 그럴까 ? 이미 'A'를 배워버렸기 때문에 더 이상 선행으로 배워야 할 스킬이 없기 때문에 0개가 된다.

이 때, 'C'는 스킬의 갯수가 '1'개로 줄어들게 될 것이다. 하지만 여전히 'C'는 선행으로 배워야 하는 스킬의 갯수가 아직 1개 남아있기 때문에 배울 수 있는 스킬은 아니다.

 

지금부터 위에서 이야기 했던 "선행으로 배워야 하는 스킬의 갯수" 를 중점적으로 문제에 접근해 볼 것이다.

선행으로 배워야 하는 스킬의 갯수를 구하는 과정을 코드로 나타내면 다음과 같다.

int Prev_Skill[26];

void Make_Prev_Skill(string Str)
{
    for(int i = 0 ; i <Str.length(); i++)
    {
        char C = Str[i];
        Prev_Skill[C - 'A'] = i;
    }
}

위의 코드를 통해서 알 수 있지만, "해당 스킬을 배우기 위해서 선행으로 배워야 하는 스킬의 갯수는 해당 스킬의 Index번호와 동일" 하다는 것을 알 수 있다.

"ABC"에서 0번 Index에 해당하는 스킬 'A'는 선행으로 배워야 하는 스킬의 갯수가 0개.

"ABC"에서 1번 Index에 해당하는 스킬 'B'는 선행으로 배워야 하는 스킬의 갯수가 1개. (A를 배워야 배울 수 있다.)

"ABC"에서 2번 Index에 해당하는 스킬 'C'는 선행으로 배워야 하는 스킬의 갯수가 2개. (A와 B 를 배워야 배울 수 있다.)

 

#2. 스킬간의 관계 표시

그럼 지금부터 선행으로 배워야 하는 스킬의 갯수를 구하기 위해서 미리 사전 작업을 진행해볼 것이다.

본인은, 가장먼저 "현재 스킬 이후에 배울 수 있는 스킬들을 Vector를 통해 저장" 하는 과정을 진행해 주었다.

예시를 가지고 진행해보자. 정해진 스킬트리가 "ABC" 라고 가정해보자.

가장 먼저, 스킬 'A'를 확인해보자. 'A'스킬 이후에 배울 수 있는 스킬들로는 'B'와 'C'가 존재한다.

그럼, Vector[A] 에다가 [ B , C ] 를 저장해 주었다.

'B'스킬 이후에 배울 수 있는 스킬로는 'C'가 있다. Vector[B] 에다가는 [ C ] 를 저장해준 것이다.

물론 ! Index번호에 알파벳이 올 수는 없기 때문에 각각의 스킬들을 Integer 형 변수로 매핑시킨 후에 삽입해 주었다.

여기에 저장되어 있는 데이터들이 어떻게 사용되는지는 밑에서 구체적으로 알아보도록 하자.

이 과정을 코드로 나타내면 다음과 같다.

vector<int> Skill[26];

void Make_Skill_Relative(string Str)
{
    for(int i = 0;  i< Str.length(); i++)
    {
        char C = Str[i];
        for(int j = i + 1; j < Str.length(); j++)
        {
            char Next = Str[j];
            Skill[C - 'A'].push_back(Next - 'A');
        }
    }
}

위의 코드에서 매개변수로 호출되어 있는 'Str'은 우리에게 주어진 solution 함수의 매개변수 'skill' 이다.

 

#3. 유저 스킬트리 Check

이제 본격적으로 정답을 구하는 과정을 진행해보자.

이 또한 예시를 가지고 진행해보자. 선행 스킬 순서가 "ABC"이고, 유저가 만든 스킬 트리가 "ABDCE" 라고 가정해보자.

우리는 유저가 만든 스킬트리를 이제 순차적으로 탐색해보면서, "선행으로 배워야 하는 스킬의 갯수가 0개인지 아닌지"만 판단을 해주면 된다. #1의 과정에서 소개한 코드를 통해서 "ABC"에서 A는 선행으로 배워야 할 스킬의 갯수가 0개, B는 1개, C는 2개라는 것을 이미 파악해둔 상태이다.

 

이제 유저가 만든 스킬트리를 보자.

가장 먼저, "A"를 확인해보자. 선행으로 배워야 하는 스킬의 갯수가 0개이다. 따라서 배울 수 있는 스킬이다.

그럼 ? 이제는 "A"를 배웠다고 표시를 해줘야 한다. 어떻게 표시를 해줄수 있을까 ??

#2에서 "현재 스킬을 배운 후에 배울 수 있는 스킬들을 Vector에 저장" 해주는 과정을 진행했었다. 이 Vector를 통해서 표시를 해줄 수 있다. A를 배운 후에 배울 수 있는 스킬들은 [ B , C ]가 있다. 그럼, 'B'와 'C'의 "선행으로 배워야 할 스킬의 갯수들을 하나씩 감소" 시켜주면 된다. 그렇게 되면 ? 'B'가 선행으로 배워야 하는 스킬의 갯수는 0개 , 'C'가 선행으로 배워야 하는 스킬의 갯수는 1개가 될 것이다.

이 후에 스킬 "B"는 선행으로 배워야 하는 스킬의 갯수가 0개이므로 배울 수 있을 것이고, 배운 후에는 이 후에 배울 수 있는 스킬들이 선행으로 배워야 하는 스킬의 갯수가 하나씩 또 감소될 것이다.

이런 과정을 반복하는 중에, 만약 "선행으로 배워야 할 스킬의 갯수가 0개가 아닌데 배우려는 경우" 가 발견되면 이는 불가능한 스킬트리라는 것을 의미한다.

 

이 과정을 코드로 나타내면 다음과 같다.

int Find_Answer(string Str, vector<string> V)
{
    int Answer = 0;
    for(int i = 0;  i < V.size(); i++)
    {
        Make_Prev_Skill(Str);
        string Str = V[i];
        bool Flag = true;
        
        for(int j = 0 ; j < Str.length(); j++)
        {
            char C = Str[j];
            if(Prev_Skill[C - 'A'] != 0) 
            {
                Flag = false;
                break;
            }
            
            for(int k = 0 ; k < Skill[C - 'A'].size(); k++)
            {
                int Next = Skill[C - 'A'][k];
                Prev_Skill[Next]--;
            }
        }
        
        if(Flag == true) Answer++;
    }
    return Answer;
}

line19 ~ 23) 부분이 "현재 스킬을 배웠을 때, 이 후에 배울 수 있는 스킬들이 가지고 있는 선행 해야 할 스킬의 갯수를 감소시키는 과정" 이다. 또한, line13) 에서보면, 현재 스킬을 배우려고 할 때, 선행으로 배워야 할 스킬의 갯수가 0개가 아니라면, 즉 ! 선행으로 배워야 할 스킬이 남아있는 경우에는 불가능한 스킬트리이므로 그대로 탐색을 종료하게 된다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int Prev_Skill[26];
vector<int> Skill[26];
 
void Make_Skill_Relative(string Str)
{
    for(int i = 0;  i < Str.length(); i++)
    {
        char C = Str[i];
        for(int j = i + 1; j < Str.length(); j++)
        {
            char Next = Str[j];
            Skill[C - 'A'].push_back(Next - 'A');
        }
    }
}
 
void Make_Prev_Skill(string Str)
{
    for(int i = 0 ; i <Str.length(); i++)
    {
        char C = Str[i];
        Prev_Skill[C - 'A'] = i;
    }
}
 
int Find_Answer(string Str, vector<string> V)
{
    int Answer = 0;
    for(int i = 0;  i < V.size(); i++)
    {
        Make_Prev_Skill(Str);
        string Str = V[i];
        bool Flag = true;
        
        for(int j = 0 ; j < Str.length(); j++)
        {
            char C = Str[j];
            if(Prev_Skill[C - 'A'] != 0) 
            {
                Flag = false;
                break;
            }
            
            for(int k = 0 ; k < Skill[C - 'A'].size(); k++)
            {
                int Next = Skill[C - 'A'][k];
                Prev_Skill[Next]--;
            }
        }
        
        if(Flag == true) Answer++;
    }
    return Answer;
}
 
int solution(string skill, vector<string> skill_trees) 
{
    int answer = -1;
    Make_Skill_Relative(skill);
    answer = Find_Answer(skill, skill_trees);
    return answer;
}