글 읽기 - 시간초과 질문입니다!

skyinyour 5년 전 0

DFS로 나름 가지치기를 하여 정답은 나오지만 시간초과가 나옵니다.

여기서 메모제이션을 사용해야하는건가요 ?

메모제이션을 여기에 적용하기도 어렵지만(제실력으로는 ㅠㅠ) 메모제이션을 했을 경우 만약에 최소값을 건너뛰어버릴 수 있을 것 같다는 생각을 하였습니다.

BFS로 도전하였지만.. 아래 주석과같이 구현해보았는데 틀린답이 나옵니다. .ㅠㅠ

방향좀 잡아주세요 .. !!

#include <iostream>
#include <queue>
using namespace std;


int N;
char map[51][51];
int mem[51][51];

bool v[51][51];
int px[4] = { -1, 0, 1, 0 };
int py[4] = { 0, 1, 0, -1 };
int cnt;
int Min = 213456789;

struct info{
	int x;
	int y;
	int len;
};
queue<info> Q;

//void bfs(int x, int y){
//
//	Q.push({ x, y,0 });
//
//	while (!Q.empty()){
//		int nx = Q.front().x;
//		int ny = Q.front().y;
//		int len = Q.front().len;
//		Q.pop();
//		if (nx == N - 1 && ny == N - 1){
//			if (Min > len) {
//				Min = len;
//			}
//		}
//		
//		
//		if (len >= Min) continue;
//		for (int i = 0; i < 4; i++){
//			int xx = nx + px[i];
//			int yy = ny + py[i];
//
//			if (xx < 0 || yy < 0 || xx >= N || yy >= N) continue;
//
//			if (!v[xx][yy]){
//				v[xx][yy] = true;
//				if (map[xx][yy] == '0'){
//					Q.push({ xx, yy, len + 1 });
//				}
//				else{
//					Q.push({ xx, yy, len});
//				}
//			}
//
//		}
//		
//		//v[nx][ny] = false;
//	}
//
//}

void dfs(int x, int y, int len){
	
	
	if (len >= Min) return;
	if (x == N - 1 && y == N - 1){
		
		if (Min > len) {
			Min = len;
		}
		return;
	}
	if (v[x][y]) return;
	v[x][y] = true;

	for (int i = 0; i < 4; i++){
		int nx = x + px[i];
		int ny = y + py[i];

		if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

		if (!v[nx][ny]){
			if (map[nx][ny] == '0'){
				dfs(nx, ny, len + 1);
			}
			else{
				dfs(nx, ny, len);
			}
			}
			
	}
	v[x][y] = false;

}

int main(){

	cin >> N;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			cin >> map[i][j];
		}
	}
	dfs(0, 0, 0);
	cout << Min;
	return 0;
}

jh05013 5년 전 1

최단거리는 무조건 BFS입니다. 왜 DFS로 시간 내에 최단거리를 찾을 수 없는지 잘 생각해 보세요.

gohyunyoung98 5년 전 0

최단거리는 아니라 DFS를 적용할수는 있는 것으로 보입니다.

(저 역시도 DFS로 해결을 했고요..)

특정 검은점 위치에 도달시, root부터 해당 노드까지의 (검->흰)변환개수를 최소값으로 저장하도록 걸러주며 저장해간다면 Pass가 가능할 것 같습니다.

jh05013 5년 전 1

그 변환 개수가 거리와 비슷한 형태라서 결국 최단거리 문제가 됩니다... 데이터가 약해서 통과되는 걸 수도 있는데 코드를 봐야 알겠군요.

jh05013 5년 전 1

@gohyunyoung98 님이 제출하신 코드는 (x, y, 거리) 로 구성된 그래프에서 DFS를 한 것으로 볼 수 있습니다. 그 그래프에는 정점이 O(n^4)개 있으므로 시간 복잡도도 O(n^4)입니다. 따라서 시간 내에는 돌아가지만, 매우 비효율적이고 입력 범위가 4배 정도만 커져도 이렇게 풀 수 없습니다.

@jh05013 조언 감사합니다. 말씀해주신 대로 N=100,1000 으로 테스트 해보니 DFS로는 입력범위가 커지는 경우에 대해서 한계가 있는 것 같습니다. BFS방식으로 해결하는게 옳을 것 같네요. 가중치가 없는 최단거리의 경우는 무조건 BFS인걸로 알고있는데, 혹시 이와 반대로 그렇다면 DFS만을 사용해야 하는 경우는 어떤 경우인지 예시정도 혹시 조언해 주실 수 있으신가요?

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

문제

문제

출처

ICPC

시간초과 질문입니다!

skyinyour 5년 전 0

jh05013 5년 전 1

rdd6584 5년 전 1

gohyunyoung98 5년 전 0

jh05013 5년 전 1

jh05013 5년 전 1

gohyunyoung98 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말