13023 ABCDE (DFS)

13023번: ABCDE

위 문제는 DFS(깊이 우선 탐색)을 활용하여 푸는 문제로

이 문제를 해결하려면 그래프에 길이가 4인 경로가 있는지 확인해야 합니다.

즉 A는 B에 연결되고 B는 C에 연결되고 C는 D에 연결되고 D는 E에 연결되는 시퀀스가 ​​존재하는지 찾아야 합니다.

 

DFS(깊이 우선 탐색)를 사용하여 그래프를 순회하고 그러한 경로가 있는지 확인할 수 있습니다.

노드를 선택하여 시작한 다음 재귀적으로 모든 이웃을 방문합니다.

 

헤더파일 및 문제 해결에 사용될 변수와 배열

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

const int MAXN = 2005;

int N, M;
vector<int> G[MAXN];
bool vis[MAXN];

 

Main 함수

int main() 
{
	// 그래프를 입력받음
        cin >> N >> M;
        for (int i = 0; i < M; i++) 
        {
                int a, b;
                cin >> a >> b;
                G[a].push_back(b);
                G[b].push_back(a);
        }

	// ABCDE 결로가 있는지 체크
        bool path_exists = false;

        for (int i = 0; i < N; i++) 
        {
        	// 방문한 노드인지 확인하는 bool배열을 false로 초기화
                fill(vis, vis + N, false);
				
                // ABCDE를 찾았다면 true를 반환함
                if (dfs(i, 0))
                {
                        path_exists = true;
                        break;
                }
        }

	// path_exists가 true면 1 아니면 0을 출력
        std::cout << path_exists ? 1 : 0;
        

        return 0;
}

 

DFS 함수

// 노드(vertex)와 깊이를 인자로 받음
bool dfs(int v, int depth) 
{		
    	// 깊이가 4라는건 ABCDE까지 왔다는 뜻이므로 true 반환
        if (depth == 4) return true;
        
        // 방문한 노드라고 체크
        vis[v] = true;
        
        bool found = false;
        for (int u : G[v]) 
        {
        	// 노드v와 연결된 모든 노드를 체크하고
           	// 방문한적 없는 노드라면 dfs 재귀
                if (!vis[u]) 
                {
                    	// 다음 노드 u와 깊이에 + 1을 하여 재귀함
                        found = dfs(u, depth + 1);
                        if (found) 
                                break;

                }
        }
        
        // 여기까지 왔다는 건 재귀가 종료 되었다는 의미이므로 
        // vis[v]를 false로 만들어주어
        // 다음 노드에서의 재탐색이 가능하게 만들어줌
        vis[v] = false;
        return found;
}