글 읽기 - 런타임에러 질문입니다 ㅠㅠ

skyinyour 6년 전 0

BFS 분류이지만..

DFS랑 BFS를 언제 적절하게 사용해야할지 몰라서 (일부러 삽질 해보고 깨닫기위해!) 일단 DFS로 풀어봤습니다.

예제는 잘 돌아가는데 12% 정도? 에서 런타임 에러가 발생하네요 ㅠㅠ

왜그런지 도저히 알 방법이 없네요 ㅠㅠ

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, M,cnt;
int Min;
int D[101][101];
int V[101][101];

int PX[4] = { 1, 0, -1, 0 }; // down right up left
int PY[4] = { 0, 1, 0, -1 };
vector<int> Vc;
void DFS(int x, int y, int l){

	

	if (x == N && y == M){
		Vc.push_back(l+1);
	}
	
	if (V[x][y] == 1) return;
	else V[x][y] = 1;
	

	for (int i = 0; i < 4; i++){
		int x_ = x + PX[i];
		int y_ = y + PY[i];

		if (x_ < 0 || x_ > N) continue;
		if (y_ < 0 || y_ > M) continue;
		if (D[x_][y_] == 0) continue;

		if (D[x_][y_] == 1){
			DFS(x_, y_, l + 1);
	
		}
	}
	V[x][y] = 0;


}
int main(){
	cin >> N >> M;

	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= M; j++){
			cin >> D[i][j];
		}
	}
	DFS(1, 1, 0);
	Min = Vc[0];
	
	for (int i = 0; i < Vc.size(); i++){
		if (Min > Vc[i]){
			Min = Vc[i];
		}
	}
	
	cout << Min;
	//system("pause");
	return 0;
}

jh05013 6년 전 1

질문 검색을 누르면 반례가 많이 나옵니다.

최단거리는 무조건 BFS입니다. DFS로는 최단거리를 바로 알수 없으므로 모든 경로를 탐색할 수밖에 없습니다. 그러면 맞게 짜더라도 시간초과가 날 겁니다.

skyinyour 6년 전 0

아하... 그런 이유였군요..! 감사합니다.

왜 BFS가 무조건 최단거리인지 이해하지 못했는데 공부해봐야겠습니다 ㅠㅠ 감사합니다 !!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

런타임에러 질문입니다 ㅠㅠ

skyinyour 6년 전 0

jh05013 6년 전 1

skyinyour 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말