3-G 재귀

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-G 와 테스트케이스 팁

작성

290

http://boj.kr/7a4cd7062f27488eb2b897aae623f48e

위와 같이 재귀로 모든 경우를 탐색하돼 백트래킹을 넣어 어차피 더 해봤자 의미 없는 경우는 제외를 해줬는데 메모리 초과가 나왔습니다.

위처럼 재귀로 해결하면서 따로 백트래킹으로 예외 처리를 해주는 것 보다 bfs를 쓰는 것이 더 효율적인가요? 아니면 재귀와 bfs의 차이는 크지 않지만 예외 처리를 visited로 안해줘서 생기는 차이인가요? 어디서 차이가 나는 것인지 궁금합니다 큰돌 선생님!!

+ visited 배열로 예외처리를 하면 효율적으로 이미 간 곳은 못 가게 되니 속도가 빨라지는 것까지 알겠습니다! 하지만 이렇게 되면 '다른 경로로 같은 이동 횟수를 가지면서 같은 지점에 도착한 경우'에는 visited 조건 문에서 제외가 되는 걸로 알고 있습니다. 이러면 최솟값이 나온 경우가 몇가지인지 알 수가 없죠.

그래서 큰돌 선생님께서 위의 코드를 통해 그 수를 세어주신 것 같은데 어떻게 세어주는 개념인지 잘 이해가 가지 않습니다.

위 그림처럼 이미 못가는 곳이 저렇다고 가정하면

위 그림처럼 이전의 값들을 참고, 참고, 참고... 이렇게 참고 해가면서 현재의 경우의 수까지 나오는 것이라고 보면 될까요?

c++코딩-테스트

답변 2

자르트

질문자

방문 처리 돼 있긴 때문에 다른 방법으로 경우의 수를 넣어주는 것이였군요! 감사합니다 :)

큰돌

지식공유자

안녕하세요 자르트님 ㅎㅎ

>> 음.. 일단은 BFS랑 백트래킹의 시간복잡도를 비교한다면 백트래킹의 경우 함수호출이 몇번 발생했냐를 기준으로 비교하는데 이 코드는 너무나도 시간복잡도가 큽니다.

아 그리고 사실 백트래킹의 시간복잡도를 계산하기가 좀 힘들긴해요. 가지치기를 하긴 하지만 그렇다고 해서 함수가 결과적으로 몇번 호출되느냐 이런거를 계산하기가 어렵거든요.

다음은 디버깅 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int n, k, x, cnt, _min = 987654321;
vector<int> ret;
int cnt22; 
void go(int here, int num) {
	cnt22++; 
	if (num > abs(n - k)) return;
	if (num > _min) return;
	if (n > k) {
		ret.push_back(n - k);
		return;
	}
	if (here > k) {
		ret.push_back(num + here - k);
		return;
	}
	if (here == k) {
		ret.push_back(num);
		return;
	}
	num++;
	go(here + 1, num);
	go(here * 2, num);
	go(here - 1, num);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	go(n, 0);

	for (int i : ret) _min = min(i, _min);
	for (int i : ret) {
		if (i == _min) cnt++;
	}
	cout << _min << "\n";
	cout << cnt << "\n";
	cout << cnt22 << "\n";
}

아주 쉬운 예제

5 17

264910

의 경우에도 앞의 숫자처럼 20만번의 함수호출을 하는 것을 볼 수 있습니다.

>> 예외처리보다는 그저 방문한 지점은 방문하지 않는 것을 의미합니다.

                } else if (visited[next] == visited[now] + 1) {
                    cnt[next] += cnt[now];
                }

이부분 말씀하시는거죠?

원래는 visited 면 continue를 하는 거지만, 최단거리로 방문하는 경우의 수를 +해야하기 떄문에 그 코드가 있는 것인데요.

잘 이해하신 거 같습니다. ㅎㅎ

조금 더 정리를 하면, 빨간색노드를 통해서 가는 최단거리 경우의 수가 있다고 해봅시다. 1이죠?

여기서 파란색으로 가는 경우의 수도 체크를 해야해요. 이 때 근데 빨간색으로 방문처리가 되어있기 때문에 이 경우의 수를 넣기 위해서 다음의 코드가 필요한 것입니다.

else if (visited[next] == visited[now] + 1) {

감사합니다.

인프런 커뮤니티 질문&답변

3-G 재귀