백준 13023 - ABCDE (C++)

 

 

여러 친구관계가 주어졌을 때, A->B->C->D->E의 관계가 존재하는지를 탐색하는 문제이다.

하나의 친구에서 4개의 관계를 걸쳐 다른 친구로 통할 수 있는 경로가 있는가를 묻는 것이다.

문제 풀이

DFS를 사용하면 어렵지 않게 해결할 수 있다.

친구관계를 노드라고 생각해보자.

위 그림과 같은 친구관계가 주어진다면, 정답이 될 수 있는 경우의 수는 1-2-4-5-6, 3-2-4-5-6 이 있을 것이다.

이 경우의 수를 찾기 위해선, 노드를 타고가며 탐색을 해야한다.

 

DFS를 이용하여, 깊이를 증가시키며 연결된 노드를 타고가다 보면, 깊이가 4가 되는 구간을 찾을 수 있다.

깊이가 4가 되는 구간이 있다면, 그 즉시 DFS를 종료하고 1을 반환하면 된다. (더이상 DFS를 할 필요가 없다.)

 

반면, 끝까지 DFS를 했음에도, 깊이가 4가 되는 구간을 찾지 못했다면 0을 반환하면 된다.

 

이 문제에서 주의해야할 점은, 모든 점을 기준으로 DFS를 다 해야한다는 것이다.

예를 들어보자.

 

1-2-4-5-6은 분명 깊이가 4가 되는 구간이다.

이 구간을 1부터 시작해서 DFS를 탐색하면 깊이가 4가되는 구간을 발견할 수 있지만, 2,4,5부터 시작하면 깊이가 4가되는 구간을 발견할 수가 없다.

 

그러므로, 1-2-4-5-6에 대해 모두 DFS를 탐색해주어야 하는 것이다.

중간에 깊이가 4가되는 지점을 발견한다면, 그 즉시 DFS를 멈추어도 되지만, 발견하지 못했다면 모든 친구를 시작점으로 하여 DFS를 진행하여야 한다.

 

풀이 코드

int NumOfMan = 0;
std::cin >> NumOfMan;

int NumOfRelationShip = 0;
std::cin >> NumOfRelationShip;

std::vector<std::vector<int>> RelationShip(NumOfMan);
for (int i = 0; i < NumOfRelationShip; i++)
{
	int First = 0;
	int Second = 0;
	std::cin >> First >> Second;

	RelationShip[First].push_back(Second);
	RelationShip[Second].push_back(First);
}

 

먼저, 사람의 수와 입력될 관계의 수를 입력받아 저장해주었고, 입력되는 관계를 벡터에 모두 저장해주었다.

관계는 양방향이기 때문에, 반드시 두 쪽에 모두 저장해주어야 한다.

isVisit.resize(NumOfMan, false);

 

다음은 방문체크 배열을 resize해주었다. DFS에 이용할 것이다.

for (int i = 0; i < NumOfMan; i++)
{
    DFS(RelationShip, i, 0);

    if (isFind == true)
    {
        break;
    }
}

 

다음은 DFS를 모든 사람을 시작으로 실행해주고 있다.

다만, 깊이가 4 이상이 되는 지점을 발견한다면 isFind를 true로 만들어줄것이고, isFind가 true가 되면 반복문을 즉시 탈출하도록 하였다.

void DFS(std::vector<std::vector<int>>& _RelationShip, int _CurIndex, int _Depth)
{
    if (_Depth == 4)
    {
        isFind = true;
        return;
    }

    isVisit[_CurIndex] = true;

    for (int i = 0; i < _RelationShip[_CurIndex].size(); i++)
    {
        int NextIndex = _RelationShip[_CurIndex][i];

        if (isVisit[NextIndex] == false)
        {
            DFS(_RelationShip, NextIndex, _Depth + 1);

            if (isFind == true)
            {
                return;
            }
        }
    }

    isVisit[_CurIndex] = false;
}

 

DFS함수 내부 코드는 위와 같다.

먼저, 현재 깊이가 4라면 isFind를 true로 바꾼 뒤, 재귀함수를 종료해주었다.

 

깊이가 4가 아니라면, isVisit를 true로 만들어준 뒤, 갈 수 있는 경로에 대해 DFS를 재귀적으로 진행하도록 하였다.

역시나, DFS진행중에도 isFind가 true가 됐음을 발견하였다면 재귀함수를 종료하도록 해주었다.

 

마지막엔 방문체크를 해제하여 DFS가 다양한 경로에 대해 탐색할 수 있도록 해주었다.

int Answer = isFind ? 1 : 0;
std::cout << Answer;

return 0;

 

DFS가 모두 끝난 뒤엔 답을 출력해주고 종료해주었다.

 

코드 전문

#include <iostream>
#include <vector>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

bool isFind = false;
std::vector<bool> isVisit;

void DFS(std::vector<std::vector<int>>& _RelationShip, int _CurIndex, int _Depth)
{
    if (_Depth == 4)
    {
        isFind = true;
        return;
    }

    isVisit[_CurIndex] = true;

    for (int i = 0; i < _RelationShip[_CurIndex].size(); i++)
    {
        int NextIndex = _RelationShip[_CurIndex][i];

        if (isVisit[NextIndex] == false)
        {
            DFS(_RelationShip, NextIndex, _Depth + 1);

            if (isFind == true)
            {
                return;
            }
        }
    }

    isVisit[_CurIndex] = false;
}

int main()
{
    Init();

    int NumOfMan = 0;
    std::cin >> NumOfMan;

    int NumOfRelationShip = 0;
    std::cin >> NumOfRelationShip;

    std::vector<std::vector<int>> RelationShip(NumOfMan);
    for (int i = 0; i < NumOfRelationShip; i++)
    {
        int First = 0;
        int Second = 0;
        std::cin >> First >> Second;

        RelationShip[First].push_back(Second);
        RelationShip[Second].push_back(First);
    }

    isVisit.resize(NumOfMan, false);

    for (int i = 0; i < NumOfMan; i++)
    {
        DFS(RelationShip, i, 0);

        if (isFind == true)
        {
            break;
        }
    }

    int Answer = isFind ? 1 : 0;
    std::cout << Answer;

    return 0;
}