글 읽기 - DFS방식의 풀이에서 오류가 나는 이유

melon940925 4년 전 0

6 6

0111111

0111110

0110000

0110111

0000000

이런 예시가 들어간다고 했을 때 y축으로 3이상 탐색을 하지 않는 이유가 무엇일까요??

#include <iostream>
#include <cstdio>

using namespace std;

int N, M;

int minimum = 100000000;
int chance = 1;//벽을 부술 수 있는 기회

int** map;
int** visit;

int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

void ScanNM() {
	cin >> N >> M;
}

int cnt = 1;
int maximum = 0;

class MAP {
public:

	void ScanMapInfo() {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				scanf("%1d", &map[i][j]);
	}

	void DFS(int x, int y) {
		if (x == M-1 && y == N - 1) {

			minimum = minimum > cnt ? cnt : minimum;
		}
		else if (Det(x, y)) {
			//x,y좌표와 visit현황 확인하기
			cout << "x:" <<x<<",y:"<<y<<",chance: "<<chance<< endl;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++)
					cout << visit[i][j] << ' ';
				cout << endl;
			}
			
			cout << endl;
			
			for (int i = 0; i < 4; i++) {
				if (visit[y][x] == 0 && map[x][y] == 1 && chance == 1) {
					visit[y][x] = 1;
					cnt += 1;
					chance -= 1;
					map[y][x] = 0;
					DFS(x + dx[i], y + dy[i]);
					cnt -= 1;
					chance += 1;
					visit[y][x] = 0;
					map[y][x] = 1;
				}


				else if (visit[y][x] == 0 && map[y][x] == 0) {
					visit[y][x] = 1;
					cnt += 1;
					DFS(x + dx[i], y + dy[i]);
					cnt -= 1;
					visit[y][x] = 0;
				}


				else if (visit[y][x] == 0 && map[y][x] == 1 && chance == 0)
					return;
				
			}
		}
	}

	
	bool Det(int x, int y) {
		if (x >= 0 && x < M && y >= 0 && y < N)
			return true;
		else
			return false;
	}

	void PrintResult() {
		if (minimum == 100000000)
			cout << -1 << endl;
		else
			cout << minimum << endl;
	}

};

void MemAlloc_2D() {
	map = new int* [N];
	visit = new int* [N];
	for (int i = 0; i < N; i++) {
		map[i] = new int[M];
		visit[i] = new int[M];
	}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			map[i][j] = 0;
			visit[i][j] = 0;
		}
}

void MemFree_2D() {
	for (int i = 0; i < N; i++) {
		delete[]map[i];
		delete[]visit[i];
	}
	delete[] map;
	delete[] visit;
}

int main() {

	MAP A;

	ScanNM();
	MemAlloc_2D();
	A.ScanMapInfo();
	A.DFS(0, 0);
	A.PrintResult();
	MemFree_2D();

	return 0;
}