백준 - 32394 4-cycle(easy)

 

핵심요소 - dfs

문제는 그래프 상에서 4개의 정점이 서로 연결되어 있는 사이클을 찾는 문제이다

처음에 단순히 dfs를 이용하며 각각의 vertex에 깊이를 부여하고 깊이의 차이가 3이면 4개 사이클이라 판단 하는 형식으로 하였다가 좀더 단순하게 풀수 있는 방법을 곰곰히 생각해 보았다 (결론은 위 방식으로도 해결은 가능하였다)

 

다른 방식은 단순하게 정점마다 4칸 깊이만 움직이며 탐색하는 것이다 

i 번째 정점에서 시작하여 4칸째에 i번째에 돌아오는 구간이 있으면 사이클을 증가시켜준다

다음으로 i번째 요소는 이미 모든 경우의 수를 확인하였으니 i+1번째 부터는 확인하지 않도록 한다

 

여기에서 시계방향의 사이클과 반시계방향의 사이클을 문제상에 동일한 사이클로 판단하니 마지막 결과에 2를 나누어 주면 문제가 해결된다

 

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<queue>

#define Fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;

typedef long long ll;

int n, m;

vector<vector<int>> adj;
vector<bool> visited;
vector<int> path;
vector<int> cycle;

ll result = 0;
int key_code = 0;

void dfs(int depth, int cur) {
	visited[cur] = true;
	path.push_back(cur);

	for (int next : adj[cur]) {
		if (depth >= 4 && key_code == next) {
			result++;
			continue;
		}

		if (depth >= 4) 	continue;

		if (!visited[next]) {
			dfs(depth + 1, next);
		}
	}

	visited[cur] = false;
	path.pop_back();
}

int main() {
	Fast;

	cin >> n >> m;

	adj.resize(n + 1);
	visited.resize(n + 1, false);
	cycle.resize(n + 1, 0);

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	for (int i = 1; i <= n; i++) {
		key_code = i;
		dfs(1, i);
		visited[i] = true;
	}

	cout << (result / 2) % 1000000007 << "\n";

	return 0;

}

 

후기

아직 4-cycle(hard)는 안풀어 보았지만 이 방식으로 안풀릴거 같다

그리고 역시 상위권 사람들의 코드를 보면 정말 신기한 방식으로 풀었는데 이해가 힘든거 보니 노력이 더 필요하다 ㅠㅠ