[성실코딩 3일차] 백준 #14923 미로 탈출***

DFS로 풀었다가 시간 초과 났습니다.

그리고 백준을 너무 오랜만에 풀어서인지 자꾸 쉬운 실수를 했다.

실수 1. DFS에서 탈출조건에서 여러가지 경우를 생각하지 않았음.

( 도착지가 1일 경우를 고려안하고 풀고있었음.)

실수 2. 방문했던 곳을 표시안했음.

위 두 가지를 놓쳐서 처음엔 틀렸습니다 여러번 받고 나중에 시간초과 뜸.

DFS C언어 구현 코드 -시간초과

#include < iostream >

using namespace std;

#define INF 987654321

int N, M;
int Hx, Hy, Ex, Ey;
int map[1001][1001];
int visited[1001][1001] = { 0, };

int answer = INF;

// 동 서 남 북
int dx[4] = { 0,0,1,-1};
int dy[4] = { 1,-1,0,0 };

void func(int _r, int _c, int _time, bool _wand) {
	// 탈출조건
	if (_r==Ex && _c==Ey) { // 현재위치가 도착지일 경우
		if (map[_r][_c] == 1) {
			if (_wand==true) {
				// 최소 경로 update
				if (_time < answer) {
					answer = _time;
				}
			}
			// _wand == false
			// -> 종료
		}
		else { // map[_r][_c] == 0
			// 최소 경로 update
			if (_time < answer) {
				answer = _time;
			}
		}
		
		return;
	}

	// 지팡이 사용
	if (map[_r][_c] == 1) {
		if (_wand == false) {
			// 더 이상 이동 못함 - 종료
			return;
		}
		else {
			// 지팡이 사용
			_wand = false; // true->false로 변경
		}
	}

	// 방문 표시
	visited[_r][_c] = -1;

	// 동서남북 4방향
	for (int k = 0; k < 4; k++) {
		int new_r = _r + dx[k];
		int new_c = _c + dy[k];
		// boundary check
		if ( (new_r<1 || new_r>N) ||
			(new_c<1 || new_c>M)) {
			continue;
		}
		// 방문하지 않은 곳만
		if (visited[new_r][new_c] != -1 ) {
			func(new_r, new_c, _time + 1, _wand);
			visited[new_r][new_c] = 0;
		}
	}
}

int main(void) {

	cin >> N >> M;
	cin >> Hx >> Hy;
	cin >> Ex >> Ey;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= M; c++) {
			cin >> map[r][c];
		}
	}

	func(Hx, Hy, 0, true);

	if (answer == INF) {
		cout << "-1" << endl;
	}
	else {
		cout << answer << endl;
	}
	
	return 0;
}