4차 도로건설 완성 코드

bfs는 테케 10개 전부 통과하는데, dfs는 테케 7부터 타임오버 나옴

#include <iostream>

#include <queue>

#include <stack>

using namespace std;

class POS{

public:

int r,c;

};

#define INF (1<<29)

int N;//지도 크기

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

int visit[110][110];

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

void Input_Data(){

cin >> N;

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

cin >> map[i];

}

}

/*

void bfs(){

queue<POS> q;

POS pos;

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

for(int j=0; j<N; j++)

visit[i][j] = INF;

visit[0][0] = 0;

pos.r = 0; pos.c = 0;

q.push(pos);

while(!q.empty()){

POS curPos = q.front();

q.pop();

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

POS nextPos;

nextPos.r = curPos.r + dir[i][0];

nextPos.c = curPos.c + dir[i][1];

if(nextPos.r < 0 || nextPos.r >=N || nextPos.c < 0 || nextPos.c >= N){continue;}

if(visit[nextPos.r][nextPos.c] > visit[curPos.r][curPos.c] + map[nextPos.r][nextPos.c] -'0'){

visit[nextPos.r][nextPos.c] = visit[curPos.r][curPos.c] + map[nextPos.r][nextPos.c] -'0';

q.push(nextPos);

}

}

}

}

*/

void dfs(){

stack<POS> s;

POS pos;

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

for(int j=0; j<N; j++)

visit[i][j] = INF;

visit[0][0] = 0;

pos.r = 0; pos.c = 0;

s.push(pos);

while(!s.empty()){

POS curPos = s.top();

s.pop();

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

POS nextPos;

nextPos.r = curPos.r + dir[i][0];

nextPos.c = curPos.c + dir[i][1];

if(nextPos.r < 0 || nextPos.r >=N || nextPos.c < 0 || nextPos.c >= N){continue;}

if(visit[nextPos.r][nextPos.c] > visit[curPos.r][curPos.c] + map[nextPos.r][nextPos.c] -'0'){

visit[nextPos.r][nextPos.c] = visit[curPos.r][curPos.c] + map[nextPos.r][nextPos.c] -'0';

s.push(nextPos);

}

}

}

}

int main(){

int ans = -1;

Input_Data(); // 입력 함수

// 코드를 작성하세요

dfs();

//bfs();

ans = visit[N-1][N-1];

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

return 0;

}