ChildView.cpp


// ChildView.cpp: CChildView 클래스의 구현
//

#include "pch.h"
#include "framework.h"
#include "school_map_design.h"
#include "ChildView.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif


// CChildView

CChildView::CChildView()
{
	m_bgBitmap.LoadBitmap(IDB_SCHOOLMAP);       // .rc 파일에 포함된 비트맵 리소스 로드

	m_selectedNode[0] = 0;
	m_selectedNode[1] = 0;
	m_selectedCount = 0;

	m_shortSelectedNode[0] = 0;
	m_shortSelectedNode[1] = 0;
	m_shortSelectedCount = 0;
}

CChildView::~CChildView()
{
}


BEGIN_MESSAGE_MAP(CChildView, CWnd)
	ON_WM_PAINT()
	ON_WM_LBUTTONDOWN()
	ON_WM_KEYDOWN()
END_MESSAGE_MAP()



// CChildView 메시지 처리기

BOOL CChildView::PreCreateWindow(CREATESTRUCT& cs) 
{
	if (!CWnd::PreCreateWindow(cs))
		return FALSE;

	cs.dwExStyle |= WS_EX_CLIENTEDGE;
	cs.style &= ~WS_BORDER;
	cs.lpszClass = AfxRegisterWndClass(CS_HREDRAW|CS_VREDRAW|CS_DBLCLKS, 
		::LoadCursor(nullptr, IDC_ARROW), reinterpret_cast<HBRUSH>(COLOR_WINDOW+1), nullptr);

	return TRUE;
}

void CChildView::OnPaint()
{
	CPaintDC dc(this); // 그리기를 위한 디바이스 컨텍스트입니다.

	// --------------------배경 비트맵 그리기-------------------
	CRect rect;
	GetClientRect(&rect);

	CDC memDC;							// 가상 메모리 DC 생성
	memDC.CreateCompatibleDC(&dc);		// 화면 DC와 호환되는 메모리 DC 생성

	CBitmap* pOld = memDC.SelectObject(&m_bgBitmap);	// 메모리 DC에 비트맵 선택

	BITMAP bm;						// 비트맵 정보 구조체
	m_bgBitmap.GetBitmap(&bm);		// 비트맵 정보 가져오기

	// 배경 비트맵을 클라이언트 영역에 맞게 그리기
	dc.StretchBlt(0, 0, rect.Width(), rect.Height(), &memDC,
		0, 0, bm.bmWidth, bm.bmHeight, SRCCOPY);

	memDC.SelectObject(pOld);		// 원래 비트맵으로 복원


	// --------------------노드 그리기-------------------
	CRect rcUpdate;					// 갱신 영역 사각형
	dc.GetClipBox(&rcUpdate); 		// 갱신 영역 가져오기

	POSITION pos = m_nodes.GetHeadPosition();	// 노드 리스트의 첫 번째 위치 가져오기
	while (pos)
	{
		Node n = m_nodes.GetNext(pos);			// 노드 가져오기

		// 노드의 번호의 크기 구하기
		CString strID;
		strID.Format(_T("%d"), n.id);

		CSize textSize = dc.GetTextExtent(strID);	// 텍스트 크기 계산

		int radius = 13; // 원의 반지름

		// 계산한 값으로 원 그리기
		CPen pen(PS_SOLID, 1, NULL_PEN);			// 테두리 없는 펜
		CBrush brush(n.selected == 2 ? RGB(255, 0, 0) : 
					 n.selected == 1 ? RGB(0, 255, 0) : 
									   RGB(0, 0, 0)); // 노드 선택 상태에 따른 브러시 색상 설정
		
		CPen* pOldPen = dc.SelectObject(&pen); 	// 펜 선택
		CBrush* pOldBrush = dc.SelectObject(&brush); // 브러시 선택

		dc.Ellipse(n.p_node.x - radius, n.p_node.y - radius,
			n.p_node.x + radius, n.p_node.y + radius);		// 지름 26인 원 그리기

		dc.SelectObject(pOldPen);			// 원래 펜으로 복원
		dc.SelectObject(pOldBrush); 			// 원래 브러시로 복원

		// 노드 ID 텍스트 그리기
		int textX = n.p_node.x - textSize.cx / 2;	// 텍스트 중앙 정렬
		int textY = n.p_node.y - textSize.cy / 2;

		dc.SetBkMode(TRANSPARENT);						// 배경 투명 설정 (찾아봤습니다.)
		dc.SetTextColor(RGB(255, 255, 255));			// 흰색 텍스트 설정
		dc.TextOut(textX, textY, strID);

	}

	// --------------------간선 그리기-------------------
	CPen edgePen(PS_SOLID, 2, RGB(0, 0, 255)); // 파란색 펜 생성
	CPen* pOldEdgePen = dc.SelectObject(&edgePen); // 펜 선택

	POSITION edgePos = m_edges.GetHeadPosition(); // 간선 리스트의 첫 번째 위치 가져오기
	while (edgePos)
	{
		Edge e = m_edges.GetNext(edgePos); // 간선 가져오기
		CPoint p1, p2;
		// 시작 노드와 끝 노드의 좌표 찾기
		POSITION nodePos = m_nodes.GetHeadPosition();
		while (nodePos)
		{
			Node n = m_nodes.GetNext(nodePos);
			if (n.id == e.s_node)p1 = n.p_node;
			if (n.id == e.e_node) p2 = n.p_node;
		}

		// 간선 그리기
		dc.MoveTo(p1);
		dc.LineTo(p2);
	}
	dc.SelectObject(pOldEdgePen); // 원래 펜으로 복원

	// -------------- 최단 거리 -------------------
	CPen shortPen(PS_SOLID, 4, RGB(255, 0, 0));
	CPen* oldPen = dc.SelectObject(&shortPen);

	POSITION s_Line = m_shortCutEdges.GetHeadPosition();
	while (s_Line)
	{
		Edge edge_Short = m_shortCutEdges.GetNext(s_Line);

		CPoint p1, p2;
		POSITION node_pt = m_nodes.GetHeadPosition();
		while (node_pt)
		{
			Node node_Short = m_nodes.GetNext(node_pt);
			if (node_Short.id == edge_Short.s_node) p1 = node_Short.p_node;
			if (node_Short.id == edge_Short.e_node) p2 = node_Short.p_node;
		}

		dc.MoveTo(p1);
		dc.LineTo(p2);
	}
	dc.SelectObject(oldPen);

}

void CChildView::OnLButtonDown(UINT nFlags, CPoint point)
{
	
	if (nFlags & MK_SHIFT) {
		// --------------------최단 경로 처리-------------------
		HitNode Hit_n = CheckHitNode(point); // 클릭한 위치에 노드가 있는지 확인

		if (Hit_n.id != -1) { // 노드가 선택된 경우
			// 선택된 노드의 selected 상태를 true로 변경
			POSITION pos = m_nodes.GetHeadPosition();
			while (pos)
			{
				Node& n = m_nodes.GetNext(pos);
				if (n.id == Hit_n.id) {
					n.selected = 2; // 노드 선택 상태로 변경
					break;
				}
			}
			// 선택된 노드 ID를 배열에 저장
			m_shortSelectedNode[m_shortSelectedCount] = Hit_n.id; // 선택된 노드 ID 저장
			m_shortSelectedCount++;

			if (m_shortSelectedCount == 2) { // 2개의 노드가 선택된 경우
				int id1 = m_shortSelectedNode[0];
				int id2 = m_shortSelectedNode[1];
				if (id1 != id2) { // 서로 다른 노드인 경우에만 최단 경로 계산
					FindShortestPath(id1, id2); // 최단 경로 계산 함수 호출
				}
				// 선택 초기화
				POSITION select_pos = m_nodes.GetHeadPosition();
				while (select_pos)
				{
					Node& n = m_nodes.GetNext(select_pos);
					n.selected = 0; // 모든 노드 선택 해제
				}
				m_shortSelectedCount = 0; // 선택된 노드 수 초기화
			}
			// 선택된 노드 시각적 표시를 위해 화면 갱신
			CRect resetSize(Hit_n.pt.x - 15, Hit_n.pt.y - 15,
				Hit_n.pt.x + 15, Hit_n.pt.y + 15); // 갱신할 영역 설정	
			InvalidateRect(&resetSize, FALSE);			// 화면 갱신
		}
	}
	else if (nFlags & MK_CONTROL) { // Ctrl 키가 눌린 상태에서 클릭한 경우
		// --------------------노드 선택 처리-------------------
		HitNode Hit_n = CheckHitNode(point); // 클릭한 위치에 노드가 있는지 확인
		 
		if (Hit_n.id != -1) { // 노드가 선택된 경우
			 
			// 선택된 노드의 selected 상태를 true로 변경
			POSITION pos = m_nodes.GetHeadPosition();
			while (pos)
			{
				Node& n = m_nodes.GetNext(pos);
				if (n.id == Hit_n.id) {
					n.selected = 1; // 노드 선택 상태로 변경
					break;
				}
			}

			// 선택된 노드 ID를 배열에 저장
			m_selectedNode[m_selectedCount] = Hit_n.id; // 선택된 노드 ID 저장
			m_selectedCount++;

			if (m_selectedCount == 2) { // 2개의 노드가 선택된 경우
				int id1 = m_selectedNode[0];
				int id2 = m_selectedNode[1];

				if (id1 != id2) { // 서로 다른 노드인 경우에만 간선 추가
					AddLine(id1, id2); // 간선 추가 함수 호출
				}

				// 선택 초기화
				POSITION select_pos = m_nodes.GetHeadPosition();
				while (select_pos)
				{
					Node& n = m_nodes.GetNext(select_pos);
					n.selected = 0; // 모든 노드 선택 해제
					CRect resetSize(n.p_node.x - 15, n.p_node.y - 15,
						n.p_node.x + 15, n.p_node.y + 15); // 갱신할 영역 설정

					InvalidateRect(&resetSize, FALSE);			// 화면 갱신

				}
				m_selectedCount = 0; // 선택된 노드 수 초기화
			}

			// 선택된 노드 시각적 표시를 위해 화면 갱신
			CRect resetSize(Hit_n.pt.x - 15, Hit_n.pt.y - 15,
				Hit_n.pt.x + 15, Hit_n.pt.y + 15); // 갱신할 영역 설정	
			
			InvalidateRect(&resetSize, FALSE);			// 화면 갱신
		}
		return; // 노드 선택 처리 후 함수 종료
	}
	else {
		// --------------------노드 추가 처리-------------------
		// 최대 노드 개수 제한
		int NextID = m_nodes.GetCount() + 1; // 다음 노드 ID 계산
		if (NextID > 99) {// 노드 ID가 99를 초과하면 추가하지 않음
			MessageBox(_T("노드가 너무 많습니다!"), _T("생성 한계"), MB_ICONWARNING | MB_OK);
			return;
		}
		// 새로운 노드 생성
		Node newNode;
		newNode.p_node = point;		// 클릭한 좌표 저장
		newNode.id = m_nodes.GetCount() + 1; // 노드 ID 할당
		newNode.selected = 0;	// 선택 여부 초기화

		m_nodes.AddTail(newNode);	// 노드 리스트에 추가

		CRect resetSize(point.x - 20, point.y - 20,
			point.x + 20, point.y + 20); // 갱신할 영역 설정

		InvalidateRect(&resetSize, FALSE);			// 화면 갱신
	}

	

	CWnd::OnLButtonDown(nFlags, point);
}

// 클릭한 곳이 점이 맞는지 확인
// 선택한 점이 있으면 그 점의 id 값 반환
// 선택한 점이 없으면 -1 반환
HitNode CChildView::CheckHitNode(CPoint p_hit)
{
	HitNode cilckedNode;
	cilckedNode.pt = CPoint(0, 0);
	cilckedNode.id = -1;

	POSITION pos = m_nodes.GetHeadPosition();
	while (pos)
	{
		Node n = m_nodes.GetNext(pos);

		int x = p_hit.x - n.p_node.x;
		int y = p_hit.y - n.p_node.y;
		
		if ((x * x + y * y) <= 169) // 원의 방정식
		{
			if (n.selected == 0) {
				cilckedNode.pt = n.p_node;
				cilckedNode.id = n.id;
				return cilckedNode;
			}
		}
	}
	return cilckedNode;
}

// 키보드 키가 눌렸을 때 호출되는 함수 (ESC 용)
void CChildView::OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags)
{
	if (nChar == VK_ESCAPE) { // ESC 키가 눌린 경우
		// 선택된 노드 초기화
		POSITION pos = m_nodes.GetHeadPosition();
		while (pos)
		{
			Node& n = m_nodes.GetNext(pos);
			n.selected = 0; // 모든 노드 선택 해제
		}
		m_selectedCount = 0; // 선택된 노드 수 초기화
		Invalidate(); // 화면 전체 갱신
	}

	CWnd::OnKeyDown(nChar, nRepCnt, nFlags);
}

void CChildView::AddLine(int id1, int id2)
{
	CPoint p1, p2;

	// 노드 ID에 해당하는 좌표 찾기
	POSITION pos = m_nodes.GetHeadPosition();
	while (pos)
	{
		Node& n = m_nodes.GetNext(pos);
		if (n.id == id1) p1 = n.p_node;
		if (n.id == id2) p2 = n.p_node;
	}

	// 거리 계산
	double length = sqrt(pow(p2.x - p1.x, 2) + pow(p2.y - p1.y, 2)); // 유클리드 거리 공식

	// 간선 추가
	Edge newEdge;
	newEdge.s_node = id1;
	newEdge.e_node = id2;
	newEdge.length = length;

	m_edges.AddTail(newEdge);

	CRect lineRect(min(p1.x, p2.x) - 3, min(p1.y, p2.y) - 3,
		max(p1.x, p2.x) + 3, max(p1.y, p2.y) + 3); // 갱신할 영역 설정

	InvalidateRect(&lineRect, FALSE);			// 화면 갱신
}

// 최단 경로 찾기 (Dijkstra 알고리즘)
void CChildView::FindShortestPath(int startID, int endID)
{
	// 기존 최단 경로 초기화
	m_shortCutEdges.RemoveAll();

	int nodeCount = m_nodes.GetCount();
	if (nodeCount <= 1) return;

	// dist / prev / visited 리스트 준비
	CList<double, double> dist;
	CList<int, int> prev;
	CList<bool, bool> visited;

	for (int i = 0; i < nodeCount; i++)
	{
		dist.AddTail(DBL_MAX);
		prev.AddTail(-1);
		visited.AddTail(false);
	}

	// dist[start] = 0
	dist.SetAt(dist.FindIndex(startID - 1), 0.0);


	// Dijkstra 시작
	for (int i = 0; i < nodeCount; i++)
	{
		// 방문하지 않은 dist가 가장 작은 node u 찾기
		int u = -1;
		double best = DBL_MAX;

		POSITION pD = dist.GetHeadPosition();
		POSITION pV = visited.GetHeadPosition();

		for (int id = 1; id <= nodeCount; id++)
		{
			double d = dist.GetNext(pD);
			bool v = visited.GetNext(pV);

			if (!v && d < best)
			{
				best = d;
				u = id;        // ID는 1 기반
			}
		}

		if (u == -1) break;

		// 방문 처리
		visited.SetAt(visited.FindIndex(u - 1), true);


		// u와 연결된 간선(Relax)
		POSITION ep = m_edges.GetHeadPosition();
		while (ep)
		{
			Edge e = m_edges.GetNext(ep);

			int v = -1;
			double w = e.length;

			if (e.s_node == u) v = e.e_node;
			else if (e.e_node == u) v = e.s_node;
			else continue;

			if (visited.GetAt(visited.FindIndex(v - 1))) continue;

			double du = dist.GetAt(dist.FindIndex(u - 1));
			double dv = dist.GetAt(dist.FindIndex(v - 1));

			if (du + w < dv)
			{
				dist.SetAt(dist.FindIndex(v - 1), du + w);
				prev.SetAt(prev.FindIndex(v - 1), u);
			}
		}
	}


	// 최단 경로 Backtracking
	int cur = endID;

	// 최단 경로 노드 색상 초기화 before applying new
	POSITION np = m_nodes.GetHeadPosition();
	while (np)
	{
		Node& n = m_nodes.GetNext(np);
		if (n.selected == 2) n.selected = 0; // 이전 최단경로 빨강 → 초기화
	}

	while (true)
	{
		int p = prev.GetAt(prev.FindIndex(cur - 1));
		if (p == -1) break;

		// 실제 간선 찾기 → m_shortCutEdges에 저장
		POSITION ep = m_edges.GetHeadPosition();
		while (ep)
		{
			Edge e = m_edges.GetNext(ep);

			if ((e.s_node == p && e.e_node == cur) ||
				(e.e_node == p && e.s_node == cur))
			{
				m_shortCutEdges.AddHead(e);
				break;
			}
		}

		// 최단 경로에 포함된 노드는 selected = 2(빨강)
		POSITION pnode = m_nodes.GetHeadPosition();
		while (pnode)
		{
			Node& n = m_nodes.GetNext(pnode);
			if (n.id == cur || n.id == p)
				n.selected = 2;
		}

		cur = p;
	}

	// 화면 전체 갱신 (최단 경로는 전체 그리기 필요)
	Invalidate(FALSE);
}