[백준 BOJ][C++]13023번 ABCDE 풀이: 그래프 & DFS

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

13023번: ABCDE

 

 이 문제는 그래프 문제로, DFS 로 해결할 수 있습니다. 

 

 그래프 생성 후, depth가 5인 경로를 찾기만 하면 되는데요!

 

 처음엔 인접 행렬로 그래프를 구현하였는데 시간 초과가 떴습니다 ㅠㅠ

 

 아마 인접 행렬은 검사하지 않아도 될 녀석들도 검사해서 그런 것 같아요.

 

 때문에 인접 리스트로 그래프를 구현한 결과 시간초과가 뜨지 않고 성공했습니다!

 

 추가로 depth가 5인 경로를 찾기만 하면 그 즉시 탐색을 끝내고 1을 출력하면 되기 때문에 depth가 5인 경로를 찾았음을 나타내는 변수 flag를 선언하여 불필요한 탐색을 없애도록 해야합니다. 

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cstdlib>
#include<cstring>

using namespace std;

bool flag = false;
int n, m;
bool visit[2000] = { false, };
vector<int> graph[2000];

void dfs(int u, int depth) {

	if (depth == 5) {
		flag = true;
		return;
	}

	for (int i = 0; i < graph[u].size(); i++) {
		int next = graph[u][i];
		if (!visit[next]) {

			visit[next] = true;
			dfs(next, depth + 1);
			if (flag) {
				return;
			}
			visit[next] = false;
		}
	}
}

int main(void) {

	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

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

		memset(visit, false, sizeof(visit));
		visit[i] = true;
		dfs(i, 1);
	}

	if (flag)
		printf("1");
	else
		printf("0");

	return 0;
}