[C++]백준13023번 ABCDE

오늘은 백준13023번 ABCDE 문제를 풀어보도록 하자.

간선의 cnt가 5면 1을 출력하는 문제였다. 인접벡터행렬을 만들어 구현했는데 만일 그냥 인접배열로 만든다면 친구관계가 아닌 사람들도 한 번씩 체크를 해주어야 하기 떄문에 TLE이 나는 문제였다.

문제는 다음과 같다.

                               [접근법]

  1. 우선 인접배열int v[2000][2000]이 아닌 vector<int>v[2000]을 생성해준다. (친구관계인 사람들만 보기 위해서)
  
  2. 그리고 방문처리가 되어있지 않은 친구로 들어가며 cnt+1을 해주고 만일 cnt>=5면 flag = true로 바꾸고 탐색을 종료한다.

                                     [코드]
#include <iostream>
#include <vector>
using namespace std;
vector<int>v[2000];
bool visit[2000];
int N, M, a, b;
bool flag = false;

void dfs(int idx, int cnt) {
	if (cnt >= 5) {
		flag = true;
		return;
	}
	for (int i = 0; i < v[idx].size(); i++) {
		if (!visit[v[idx][i]]) {
			visit[v[idx][i]] = true;
			dfs(v[idx][i], cnt + 1);
			if (flag) {
				return;
			}
			visit[v[idx][i]] = false;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i = 0; i < N; i++) {
		dfs(i, 0);
		if (flag) {
			cout << 1;
			return 0;
		}
	}
	cout << 0;
}