[백트레킹] 점들을 연결했을 때 최소 거리 구하기

마우스로 10개 이하의 점을 임의로 찍어서 모든 점들을 연결했을 때 가장 짧은거리를 그려보자.

 <소스코드>

#include<opencv2/opencv.hpp>
#include <iostream>
#include <random>
#include <time.h>
#include <stack>


#define nonMouse "Non MouseEvent"
#define useMouse "Mouse Event"

using namespace std;
using namespace cv;
struct temp { int x, y; }pt[10], temp2;
stack<temp>S, MIN_D;
int visit[10];
temp Min_pt[10];
int Min_dis = 2147438646;
int dot;
int temp_distance;

void draw_line(int s, int n) { //n은 그려야할 남은 선 개수 s는 현재 점
	if (n == 0) {
		temp2.x = pt[s].x;
		temp2.y = pt[s].y;
		S.push(temp2);
		if (temp_distance <= Min_dis) {
			Min_dis = temp_distance;
			MIN_D = S;
		}
		S.pop();
		return;
	}
	else {
		for (int i = 0; i < dot; i++) { //i는 다음점
			if (visit[i] == 0) {
				temp2.x = pt[s].x;
				temp2.y = pt[s].y;
				S.push(temp2);
				int stoi = (pt[s].x - pt[i].x)*(pt[s].x - pt[i].x) + (pt[s].y - pt[i].y)*(pt[s].y - pt[i].y); //거리 구할 때 비교만 할 것이므로 굳이 루트처리 안해줌
				temp_distance = temp_distance + stoi;
				visit[i] = 1;
				draw_line(i, n - 1);
				visit[i] = 0;
				temp_distance = temp_distance - stoi;
				S.pop();

			}
		}
	}
}

void onMouseEvent(int event, int x, int y, int flags, void * dstImage) {
	Mat mouseImage = *(Mat*)dstImage;

		switch (event) {
			//클릭이벤트
		case CV_EVENT_LBUTTONDOWN:
			cout << Point(x, y) << endl;
			pt[dot].x = x;
			pt[dot].y = y;
			Point pin(x, y);
			circle(mouseImage, pin, 1.5, Scalar(0, 0, 255), 2); // 좌표를 시각화
			dot++;
			cout << "점 :" << dot << "개 입력" << "\n";
			
		
			
			break;
		}
	
		imshow(useMouse, mouseImage);
	}

int main() {
	srand(time(NULL));
	Mat dstImage(500, 500, CV_8UC3, Scalar(255, 255, 255));
	Mat srcIamge = dstImage;
	if (srcIamge.empty()) {
		return -1;
	}

	//imshow(nonMouse, srcIamge);
	imshow(useMouse, srcIamge);
	setMouseCallback(useMouse, onMouseEvent, (void*)&srcIamge);
	int inkey;
	while(1) {
		inkey = waitKey();
		if (inkey == 13) {
			for (int i = 0; i < dot; i++) {
				visit[i] = 1;
				draw_line(i, dot - 1); // 선의 개수 = 점 - 1
				visit[i] = 0;
			}

			while (1) {
				Point pin1(MIN_D.top().x, MIN_D.top().y);
				MIN_D.pop();
				if (!MIN_D.empty()) {
					Point pin2(MIN_D.top().x, MIN_D.top().y);
					line(dstImage, pin1, pin2, Scalar(0, 0, 0), 1);
				}
				else break;
			}
	
			break;
		}
		cout <<"엔터"<< endl;
	}
	waitKey();
	return 0;
}

점을 찍고 엔터를 치면 최소 거리의 길을 그려준다.

기존에 실행시 랜덤으로 2~10개의 점을 찍어서 그려주던 코드에서 마우스 이벤트만 추가한 것이라 코드가 지저분하다.

<실행결과>