13023 ABCDE C++ 문제 설명과 풀이

안녕하세요 판타지코딩월드입니다!

 

오늘은 13023 ABCDE 문제 C++로 문제 설명하고 풀어보겠습니다.

---

1. 문제 설명

 

0번부터 N-1번까지 친구들 중에 A와 B가 친구이고, B가 C와 친구이고, C와 D가 친구이며 D가 E와 친구인 관계가 존재하는지를 찾는 문제이다. DFS를 활용하기 때문에 간단히 이야기하면 depth가 5까지 갈 수 있는 관계인지를 묻는 것이다. 

 

사람의 수는 N, 친구 관계 수 M을 입력 받아 M개의 줄에 입력한 관계를 배열이나 벡터에 저장하고 DFS를 활용해서 풀면 된다.

 

 

2. 문제 풀이

 

우선 그림으로 그려보면서 어떤 모양인지 이해해야 한다. 그런데 그림을 그렸을 때 오히려 헷갈릴 수 있는 부분이 있다. 아래의 그림을 보자.

ABCDE 참고

 

0과 1, 1과 2, 2와 3, 3과 4 이렇게 4개의 관계가 만족하면 DFS 함수의 depth가 5로 만족한다. 이 경우는 직관적으로 연결되어 있기에 헷갈리지는 않는다. 그럼 아래의 예시에서 depth 몇인지 구해보자.

ABCDE 참고

 

우선 연결 만으로는 조건을 만족하는 것으로 보인다. 0과 3, 3과 2, 2와 1, 1과 4 이 순서로 보면 충분히 만족한다. 그런데 DFS 함수의 모습을 생각해보면 보통 Visit 또는 Check라는 이름의 배열을 활용해서 방문 처리를 하고, 한 번 방문했던 곳은 다시 방문하지 않도록 하기 때문에 1->0, 0->3, 3->2, 2->1, 1->4 이런 순서로 생각을 하게 된다면 1->0을 했기 떄문에 2->1, 1->4는 안 되지 않을까?라는 생각을 할 수 있다. 그래서 이번 문제에서 필요한 개념이 바로 '백트래킹'이다.

 

• 백트래킹 (BackTracking) : DFS 함수에서 분기가 있을 때, 다른 분기도 확인해볼 수 있도록 하는 기법

방문 처리를 하고 다시 DFS를 수행한 후, 다른 경우의 수를 찾기 위해 방문 처리를 해제한 후 나머지 코드를 실행하는 것이다. 해당 코드는 아래와 같다.

for(int i=0; i<N; i++)
{
    check[i] = true;
    dfs(i, 1);
    if(finishVal)
        break;
    check[i] = false;
}

 

이 코드는 DFS 함수를 시작하기 위해 0부터 N-1까지의 수 중 하나를 start 인자로 주는 것이다. check 처리를 한 후 DFS 수행이 완료되면 다시 나와 check 처리를 해제한다. 그리고 다른 경우의 수도 확인을 한다. 또는 memset 함수를 활용해서 check을 0으로 초기화 시켜도 된다.

 

• DFS와 백트래킹

또 다른 백트래킹 적용 코드인 DFS 함수 부분을 보자.

int N, M;
int rst = 0;
vector<int> vec[2001];
bool check[2001];
bool finishVal = false;

void dfs(int start, int cnt)
{
    if(cnt==5)
    {
        rst = 1;
        finishVal = true;
        return;
    }
    for(int i=0; i<vec[start].size(); i++)
    {
        int next = vec[start][i];
        if(check[next])
            continue;
        check[next] = true;
        dfs(next, cnt+1);
        check[next] = false;
    }
}

 

깊이가 5일 경우 탐색을 중단하고 결과를 "1"로 출력하는 코드이다. start 인자와 연결 된 다음 값을 방문 처리 후, DFS 함수를 실행하여 깊이를 탐색한다. 각각의 탐색에서 나올 수 있는 경우의 수를 모두 가보기 위해 탐색 종료 후 다시 방문 처리를 해제하는 것이다. 이렇게 하면 방문해볼 수 있었지만 방문하지 않은 경우의 수를 놓치지 않을 수 있다. 이러한 기법을 바로 백트래킹이라고 한다. 

 

백트래킹을 활용할 경우 시간초과 문제가 나올 수 있다. 백트래킹 없이 DFS 함수를 실행하는 것과 비교해서 추가적으로 여러 가지 경우를 확인해보기 때문에 더 많은 시간을 사용할 수 밖에 없기 때문이다. 그래서 방문 처리와 방문 해제 처리를 적절한 위치에 하고, 원하는 값을 찾았다면 바로 return 처리로 함수를 종료해 주는 것이 좋다.

 

 

3. 전체 코드

 

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

int N, M;
int rst = 0;
vector<int> vec[2001];
bool check[2001];
bool finishVal = false;

void dfs(int start, int cnt)
{
    if(cnt==5)
    {
        rst = 1;
        finishVal = true;
        return;
    }
    for(int i=0; i<vec[start].size(); i++)
    {
        int next = vec[start][i];
        if(check[next])
            continue;
        check[next] = true;
        dfs(next, cnt+1);
        check[next] = false;
    }
}
int main()
{
    cin >> N >> M;
    for(int i=0; i<M; i++)
    {
        int a, b;
        cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    
    for(int i=0; i<N; i++)
    {
        check[i] = true;
        dfs(i, 1);
        if(finishVal)
            break;
        check[i] = false;
    }
    
    if(rst==1)
        cout << "1" << endl;
    else
        cout << "0" << endl;
    
    return 0;
}

---

오늘은 C++로 DFS, 백트래킹을 활용해 문제를 풀어보았습니다. DFS와 백트래킹을 활용할 떄 시간초과가 발생할 수 있는 요소에 대해 생각하면서 문제 풀어보시면 좋겠습니다.

 

감사합니다!