3-O go 함수 질문 드립니다.

작성한 질문수 19

0

#include <bits/stdc++.h>
using namespace std;
int n = 5, k = 3, a[5] = {1, 2, 3, 4, 5};

void print(vector<int> b){
	for(int i : b)cout << i << " ";
	cout << '\n';
}

void combi(int start, vector<int> b){
	if(b.size() == k){
		print(b);
		return;
	}
	
	for(int i = start + 1; i < n; i++){
		b.push_back(i);
		combi(i, b);
		b.pop_back();
	}
	
	return;
}

int main() {
	vector<int> b;
	combi(-1, b);
	return 0;
}

저도 이해하기 힘들었는데 알고리즘교안에 있는 재귀를 이용한 조합

이 부분과 가장 유사해 보입니다.

0

안녕하세요 ㅎㅎ

    for(int i = here; i <= h; i++){
        for(int j = 1; j <= n; j++){
            if(visited[i][j] || visited[i][j - 1] || visited[i][j + 1]) continue;
            visited[i][j] = 1;
            go(i, cnt + 1);
            visited[i][j] = 0;
        }
    }

앞의 코드를 보면 here부터 들어가고 있죠? 그러면서 here ~ h까지 들어가면서 here부분의 j = 1부터 n까지 모든 가로 라인을 다 확인하고 있는 것을 볼 수 있습니다.

즉 이부분은 세로라인 here의 가로라인을 중복해서 확인하는 것입니다. 따라서 here의 가로에 해당하는 모든 경우의수를 다 확인합니다.

그렇기 때문에 과거의 here - 1을 탐색할 필요가 없습니다. 이미 모든 경우의수를 다 확인하는 코드니까요.

예를 들어

here가 1일 때 {1, 1}, {1, 2} ... {1, n} 확인하고 {2, 1} .. 이런식으로 호출되겠죠. 이 때 {2, 1}에서 다시 {1, 1}을 확인할 필요가 있을까요? 이미 모두 확인했는데요?

그렇기 때문에 cnt = 0 에서 놓았던 가로선 보다 같거나 아래 위치에 가로선을 놓아야한다는 조건이 도출되는 것입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.