stack으로 dfs 구현

#include <iostream>

#include <stack>

#include <algorithm>

#include <cstdio>

using namespace std;

int N;//지도 크기

char map[110][110];//지도 정보

int cMap[110][110];

int dirArray[4][2] = { {-1,0}, {0,1}, {1,0}, {0,-1}};

int ans = 10e8;

int sum;

#define VISITED 2

#define BACKTRACKED 3

class POS{

public:

int x=0;

int y=0;

int curDir=0;

int sum=0;

};

void Input_Data(){

cin >> N;

for (int i = 0; i < N; i++){

cin >> map[i];

}

}

void dfs(){

POS cur;

stack<POS> s;

cur.x = 0;

cur.y = 0;

cur.curDir = 0;

cur.sum=0;

s.push(cur);

while(true){

cMap[cur.x][cur.y] = VISITED;

printf("[%d,%d] ", cur.x, cur.y);

if(cur.x == N-1 && cur.y == N-1){

ans = sum < ans ? sum : ans;

}

bool forwarded = false;

for(int dir=cur.curDir; dir<4; dir++){

POS nextPos;

nextPos.x = cur.x + dirArray[dir][0];

nextPos.y = cur.y + dirArray[dir][1];

nextPos.curDir = 0;

if( (nextPos.x >= 0 && nextPos.x < N && nextPos.y >= 0 && nextPos.y< N) && cMap[nextPos.x][nextPos.y] == 0){

cur.curDir = dir+1;

s.push(cur);

cur = nextPos;

forwarded = true;

break;

}

}

//더이상 갈 곳 없을 경우

if(!forwarded){

cMap[cur.x][cur.y] = 0;

if(s.empty()){

cout << "No path exists. \n";

break;

}

cur = s.top();

s.pop();

}

}

}

int main(){

Input_Data(); // 입력 함수

// 코드를 작성하세요

dfs();

cout << ans << endl; // 정답 출력

return 0;

}