# DFS(깊이우선탐색)으로 최단 거리값 계산하기.

DFS(깊이우선탐색)으로 주어진 M x N ( M, N은 같을 수 있다. ) 2차원 맵에서

시작점에서 목표지점까지 최단 거리 값을 계산한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

#define WALL 0 #define MOVABLE 1 #define PASSED 2 void Pathfinding(int x, int y, int length, int& minPathCnt, vector<vector<int>>& maps, const int& maxX, const int& maxY); int solution_dfs_pathfinding(vector<vector<int>> maps) { int row = maps.size(); int colmnu = maps[0].size(); int minPathCnt = row * colmnu; Pathfinding(0, 0, 1, minPathCnt, maps, row - 1, colmnu - 1); if (minPathCnt == row * colmnu) minPathCnt = -1; return minPathCnt; } void Pathfinding(int x, int y, int length, int& minPathCnt, vector<vector<int>>& maps , const int& maxX, const int& maxY) { if ((x == maxX) && (y == maxY)) { if (minPathCnt > length) { minPathCnt = length; } return; } maps[x][y] = PASSED; if ((x < maxX) && maps[x + 1][y] == MOVABLE) { Pathfinding(x + 1, y, length + 1, minPathCnt, maps, maxX, maxY); } if ((x > 0) && maps[x - 1][y] == MOVABLE) { Pathfinding(x - 1, y, length + 1, minPathCnt, maps, maxX, maxY); } if ((y > 0) && maps[x][y - 1] == MOVABLE) { Pathfinding(x, y - 1, length + 1, minPathCnt, maps, maxX, maxY); } if ((y < maxY) && maps[x][y + 1] == MOVABLE) { Pathfinding(x, y + 1, length + 1, minPathCnt, maps, maxX, maxY); } maps[x][y] = MOVABLE; }