[SWEA] 6057. 그래프의 삼각형

문제

정점이 N개, 간선이 M개 있는 그래프가 주어진다. 정점에는 1번에서 N번까지의 번호가 붙어 있다.

이 때, i번 정점과 j번 정점 사이에, j번 정점과 k번 정점 사이에, k번 정점과 i번 정점 사이에

모두 간선이 있는 ( i, j, k ) (단, i < j < k )를 삼각형이라고 하자.

삼각형의 개수를 구하는 프로그램을 작성하라.

 

풀이방법

DFS(깊이 우선 탐색) 알고리즘을 활용해 문제를 해결한다.

 

삼각형을 만드는 경우는 정점 3개가 cycle을 형성할 때 삼각형이 만들어진다.

 

정점 3개로 이루어진 사이클의 모든 개수를 다 찾는다.

 

예를 들어, 1번 정점부터 시작했을 때, 1번 정점에서 갈 수 있는 정점을 모두 방문한다. 현재 방문한 정점의 개수는 1이다(1번 정점 제외)

 

각 방문한 정점에서 갈 수 있는 정점을 모두 방문한다. 현재 방문한 정점의 개수는 2이다.

 

마찬가지로 방문한 정점에서 갈 수 있는 정점을 모두 방문하는데 이때, 방문한 정점이 1번일 경우 사이클을 형성하는 경우이다. 

 

이러한 방식으로 각 정점에서 만들 수 있는 모든 사이클의 수를 찾는다.

 

소스코드

package samsung;

import java.util.*;

public class s_6057 {
	static int[][] a;
	static int n;
	static int[] v;
	static int cnt;
	
	public static void dfs(int end, int vertex, int depth) {
		if(depth == 3) {
			if(end == vertex)
				cnt++;
		}else {
			for(int i = 0; i < n; i++) {
				if(v[i] == 0 && a[vertex][i] == 1) {
					v[i] = 1;
					dfs(end, i, depth + 1);
					v[i] = 0;
				}
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			n = sc.nextInt();
			int m = sc.nextInt();
			a = new int[n][n];
			v = new int[n];
			cnt = 0;
			
			for(int i = 0; i < m; i++) {
				int v1 = sc.nextInt() - 1;
				int v2 = sc.nextInt() - 1;
				a[v1][v2] = 1;
				a[v2][v1] = 1;
			}
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(j < i) {
						v[j] = 1;
					}
					else {
						v[j] = 0;
					}
				}
				for(int j = 0; j < n; j++) {
					if(a[i][j] == 1 && v[j] == 0) {
						v[j] = 1;
						dfs(i, j, 1);
					}
				}
			}
			System.out.println("#" + t + " " + cnt);
		}
	}
}