지름길 까지 구한 출력문.

최근 소스코드 : 지름길 코드 추가.

#include <iostream>
using namespace std;
#include <string>

#include <vector>
#include <limits.h>
#include <algorithm>
#include <map>
#include <future>
#include <thread>
#include <numeric>
#include <stack>
#include <queue>
#include <memory>
#include <set>
#include <string>
#include <stack>
#include <mutex>


int n, m;// y , x

void MakePath(vector<pair<int, int>> &_path , vector<vector<pair<int, int>>>&_parent)
{
	// 종착지를 기준으로 해서 탐색하기만 하면됨. 
	// parent를 역으로 해서 추적하자.

	_path.push_back({ n - 1, m - 1 });
	pair<int, int> target = _parent[n - 1][m - 1];

	while (1)
	{
		_path.push_back(target);
		target = _parent[target.first][target.second];

		if (target.first == 0 && target.second == 0)
			break;
	}

	_path.push_back({ 0,0 });


}


void bfs(vector<vector<int>>&_v, vector<vector<bool>>&_visited)
{
	//queue<pair

	// 상하좌우
	pair<int, int>dir[4] = { {1,0},{-1,0},{0,-1},{0,1} };

	queue<pair<int, int>>q;// first 가 y , second 가 x
	q.push({ 0,0 });
	_visited[0][0] = true;

	vector<vector<pair<int, int>>> parent(n , vector<pair<int,int>>(m));
	

	while (!q.empty())
	{
		pair<int,int> curPoint = q.front();// x, y 
		q.pop();

		if (curPoint.first == n - 1 && curPoint.second == m - 1)
		{
			cout << _v[n - 1][m - 1] << endl;
			
			// 경로 만들자.
			vector<pair<int, int>> path;
			MakePath(path, parent);

			reverse(path.begin(), path.end());
			cout << "path 경로는 " << endl;

			for (auto& iter : path)
			{
				cout << "y, x 좌표는 ";
				cout << "[ " << iter.first << "," << iter.second << " ]"<< endl;
			}

			return;
		}


		for (int i = 0; i < 4; ++i)
		{
			int nextY = curPoint.first + dir[i].first;
			int nextX = curPoint.second + dir[i].second;

			// 범위 체크
			if (nextX < 0 || nextX >= m
				|| nextY < 0 || nextY >= n)
			{
				continue;
			}

			if (_visited[nextY][nextX] == true)
				continue;

			if (_v[nextY][nextX] == 1)
			{
				_v[nextY][nextX] += _v[curPoint.first][curPoint.second];
				// 진입하자마자 방문 체크하자.
				_visited[nextY][nextX] = true;
				q.push({ nextY, nextX });
				parent[nextY][nextX] = curPoint;
			}
		}
	}




}

int main()
{
	cin >> n >> m;

	vector<vector<int>>v(n, vector<int>(m, 0));
	vector<vector<bool>>visited(n, vector<bool>(m, false));

	string s;

	for (int i = 0; i < n; ++i)
	{
		cin >> s;
		for (int j = 0; j < m; ++j)
		{
			v[i][j] = s[j] - '0';
		}
	}

	//for (int i = 0; i < n; ++i)
	//{
	//	for (int j = 0; j < m; ++j)
	//	{
	//		cout << v[i][j];
	//	}
	//	cout << endl;
	//}

	// 0,0 부터 n,m 까지 가자.

	// 최소비용으로 가야하니까. bfs 로 가자. 
	// 이전 노드가 가지고 있는 것만큼 더해주면서 전진.
	bfs(v, visited);

}

소스코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n;
int m;

int v[200][200];

int cnt = 0;

int dY[] = { 1,-1,0,0 };
int dX[] = { 0,0,-1,1 };


void bfs()
{
	queue<pair<int, int>>q;
	q.push({ 0,0 });

	while (!q.empty())
	{
		int curY = q.front().first;
		int curX = q.front().second;
		q.pop();

		
		if (curY == n - 1 && curX == m - 1)
		{
			return;
		}

		for (int i = 0; i < 4; i++)
		{
			int nY = curY + dY[i];
			int nX = curX + dX[i];

			if (nY < 0 || nY >= n
				|| nX < 0 || nX >= m)
				continue;

			if (v[nY][nX] == 0)
				continue;

			q.push({ nY, nX });
			v[nY][nX] = v[curY][curX] + 1;
		}


	}
}


int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
	
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%1d", &v[i][j]);
		}
	}

	bfs();

	cout << v[n - 1][m - 1];
}