글 읽기 - dfs 로는 못푸나요ㅠㅠ

wiz9243 6년 전 0

dfs 로 역추적해서 찾으려 했는데 숫자가 커지면 비정상종료되네요ㅜ 뭐가 문제일까요?

#include<iostream>
#include<cstring>

#define MAX 100005
using namespace std;

int d[MAX];
int S, E;



void dfs(int x) {
	if ( x == S )return;
	
	if ( x - 1 >= 0 && d[x - 1] > d[x] + 1 ) {
		d[x - 1] = d[x] + 1;
		dfs(x - 1);
	}
	if ( x + 1 <= E && d[x + 1] > d[x] + 1 ) {
		d[x + 1] = d[x] + 1;
		dfs(x + 1);
	}
	if ( !( x % 2 ) && d[x / 2] > d[x] + 1 ) {
		d[x / 2] = d[x] + 1;
		dfs(x / 2);
	}
}

int main() {
	cin >> S >> E;
	if ( S >= E ) cout << S - E;
	else {
		for ( int i = E; i >= 0; i-- )d[i] = E - i;
		d[E] = 0;
		if ( E % 2 )dfs(E - 1);
		else dfs(E);
		cout << d[S];
	}

	return 0;
}

djm03178 6년 전 0

함수 호출 정보와 파라미터 등은 프로그램의 메모리 영역 중 스택 영역에 할당됩니다. 스택 영역은 실제 물리 메모리 제한과는 별개로 기본적으로 작게 설정되어 있습니다. 윈도우즈의 경우 1MB, 리눅스의 경우 8MB라고 합니다.

이 문제의 경우 10만에서 0을 찾아가는 경로를 생각해보면 10만, 99999, 99998, 99997... 이렇게 찾아내려가는 수밖에 없는데, 이 경우 재귀호출이 매우 깊어지게 됩니다. 이를 계속 반복하다 보면 결국 스택의 메모리 제한을 초과하게 됩니다.

VS의 경우 디버그 모드로 실행해보면 이런 경우 Stack Overflow라는 메시지를 보여줍니다.

wiz9243 6년 전 0

근데 main함수 코드상에서 애초에 제가 -1 걸음을 통해 가능것을 초기값으로 설정했기 때문에 dfs 안의 조건판별문에서 false 가 되기 때문에 예시로 들었던 경로로 깊어지지는 않지 않을까요?

djm03178 6년 전 1

아 제가 대충 눈으로만 보고 답변했는데 저 케이스로는 안 되겠군요.

그런데 저는 릴리즈 모드로 실행해보면 에러가 나는 경우는 잘 못 찾겠네요. 디버그 모드로 돌리면 컴파일러가 임의로 넣는 추가 정보들 때문에 50000 99999 같은 케이스에서 스택 오버플로가 나긴 합니다.

그리고 이걸 해결하더라도, DFS로는 아무래도 시간초과를 피할 수 없을 것 같네요.

graykode 5년 전 0

dfs로 풀 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
int go(int n, int k) {
	if (n >= k) return n - k;
	if (k % 2 == 0) return min(k - n, go(n, k / 2) + 1);
	else return min(go(n, k + 1), go(n, k - 1)) + 1;
}
int main() {
	int n, k; cin >> n >> k;
	if (n == 0) cout << 1 + go(1, k);
	else cout << go(n, k);
}

graykode 5년 전 0

그래도 고민해서 궅이 dfs로 푸는 것 보다 bfs로 푸는게 훨씬 구조상 깔끔라고 메모리나 시간 복잡도 부근에서도 좋을것 같네요..

djm03178 5년 전 1

제약 조건들 때문에 그리디하게 경우의 수를 줄여서 DFS 커팅이 되는군요. go 함수도 최대 12916번밖에 호출이 안 되네요(0 87381). 물론 이게 이런 종류의 문제를 푸는 일반적인 방법은 아니지만, 조건을 잘 이용했다고 볼 수 있겠네요.

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

문제

문제

출처

ICPC

dfs 로는 못푸나요ㅠㅠ

wiz9243 6년 전 0

djm03178 6년 전 0

wiz9243 6년 전 0

djm03178 6년 전 1

graykode 5년 전 0

graykode 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말