[그래프][DFS]그래프의 모든 간선 지나기

문제

그래프의 모든 간선을 DFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 정점 번호는 1번부터 N번까지이다.

 

 

입력

첫째 줄에 정점의 개수 n, 간선의 개수 k가 주어진다. 다음 k개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 입력으로 주어지는 간선은 양방향이다.

 

출력

방문된 점을 순서대로 출력하면 된다.

 

예시)

 

 

코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int A[50][50] = { 0 }; //인접행렬 만들 2차원 배열, 인접행렬 : 그래프의 연결 방식을 표시
int n, k, a, b;
int check[50][50] = {0}; //체크배열 : 지나간 간선을 표시
int R[50] = { 0 }; //report배열 : 지나간 노드를 순서대로 표시

void input() {  //인접행렬 만들기
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= k; i++) {
		scanf("%d %d", &a, &b);
		A[a][b] = 1; //간선이 양방향이기 때문에 대칭으로 인접행렬 만들기
		A[b][a] = 1;


	}
}
void q(int os,int s, int L) {
	check[os][s] = 1; //지나간 간선 표시
	check[s][os] = 1; //지나간 간선 표시
	R[L] = s; //지나간 노드 표시


	//출력조건 : 지나간 간선의 개수가 주어진 간선의 개수와 일치하면 출력
	if (L == k) { 
		for (int i = 0; i <= k; i++) {
			
			printf("%c",R[i]+64); //아스키 코드를 이용하여 1:A, 2: B.... 로 출력
				


		}
		//for(int i = 1; )
		printf("\n");
		
		//리셋 : 리턴하기 전에 현재 간선을 체크배열에서 삭제
		check[os][s] = 0;
		check[s][os] = 0;
		return;
	}

	//n진 트리 : 존재하는 모든 노드 중 현재 노드와 연결되어 있고, 지나가지 않은 간선으로 연결되어 있는 노드들로 이동함
	for (int e = 1; e <= n; e++) {
		if (A[s][e] == 1 && check[s][e] == 0)q(s,e, L + 1);
	}

	//현재 위치에서 더 이상 움직일 간선이 없으모로 현재 간선을 체크배열에서 삭제
	check[os][s] = 0;
	check[s][os] = 0;


}

int main() {
	input();
	for (int s = 1; s <= n; s++) {
		R[0] = s;
		for (int e = 1; e <= n; e++) {
			if (A[s][e] == 1 && check[s][e] == 0)q(s, e, 1);
		}
	}
	
	return 0;

}

 

입력	출력