[백준] 알고리즘 13023번 - ABCDE 문제

문제

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

13023번: ABCDE

소스코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<int> g[2000];
bool visted[2000], answer;

void dfs(int index, int cnt) {
	if (cnt == 5) {
		answer = true;
		return;
	}
	visted[index] = true;
	for (int i = 0; i < g[index].size(); i++) {
		int next = g[index][i];
		if (visted[next]) continue;
		visted[next] = true;
		dfs(next, cnt+1);
		if (answer) return;
	}
	visted[index] = false;
	return;
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) { // 양방향 설정
 		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i = 0; i < n; i++) {
		dfs(i, 1);
		if (answer) {
			cout << "1";
			return 0;
		}
	}
	cout << "0";
}

해설

조건에 맞게 탐색을 해줘야한다.

A->B->C->D->E 즉 DFS로 해결하였을때 깊이가 5가되면 조건에 성립하여 1을 출력하면된다.

방문처리를 하지않을 경우 시간초과가 나게되므로 DFS를 돌때 조건이 부합하지 않을때는 꼭 return을 해줘야한다.

문제에서는 양방향으로 해결하면되고, 백터를 이용한 인접리스트를 사용한다.

• 인접행렬 - 공간의 낭비가 심하지만, o(1)만큼 거리가 이어져있나 아니면 가중치를 알 수 있다.
• 인접리스트 - 공간낭비는 인접행렬보다 작다.