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

제 설명이 부족했던 것 같습니다.

엄밀히 말하자면 모든 경우에 parti벡터가 0~3개의 원소를 갖는 조합을 구하는 것이 아니라,

nC0 조합 생성 -> 체크 -> 실패 시 nC1 조합 생성 -> 실패 시 nC2 조합 생성 -> 실패 시 nC3 조합 생성 -> 실패 시 -1 출력

이런 흐름을 가집니다. 이에 백트래킹적 성격이 내포되어있다고 생각했습니다. 1개의 사다리만 추가해서 i번째 사다리가 i번이 나온다면 더 exit(0)를 호출해서 코드를 종료시키기 때문이죠.

예제에서 정답이 -1인 것과 2인 것을 실행해보면 -1은 0~3까지의 모든 조합을 체크해보지만 정답이 2인 것은 nC2의 정답이 되는 조합이 나올 때까지만 체크합니다.

(선생님의 코드가 dfs형식이라면 저는 bfs형식인 것 같아 본문에서 백트래킹을 따로 사용하지 않았다고 말씀드린겁니다. 1개 또는 2개의 사다리를 추가해서 정답이 나오면 이후는 체크하지 않으니까요.)

제 코드에서 시간을 줄일 수 있는 방법이 뭐가 있을까 고민하다가, 2차원 사다리 벡터를 기존에는 레퍼런스로 전달해서 1. 사다리를 설치하고 2. 체크한 후 3. 사다리를 제거 (원복) 하는 형태로 있던걸 수정해서, 레퍼런스가 아닌 값 복사로 체크 함수를 호출한 다음 3번의 원복하는 과정을 없애도 봤습니다만 똑같이 9%에서 시간초과가 생깁니다.

http://boj.kr/a6456e7dd8e3435f8742252d77a0e474

깐깐한 문제다~ 라고 여기고 넘기는게 좋을지,, 고민입니다.

감사합니다.

일단은.

함수호출 부분에 있어서 더 많은 함수가 호출되는 경우의 수가 있습니다.

수강생님 코드 : 디버그 추가

#include <bits/stdc++.h>
using namespace std;

int N, M, H, a, b;
int cnt2 = 0;
bool isDone = false;
void check(vector<vector<int>> vertical, vector<pair<int, int>> parti)
{
	int num = parti.size();

	// add
	for (int it = 0; it < num; ++it)
	{
		pair<int, int> p = parti[it];
		vertical[p.first][p.second] = p.second + 2;
		vertical[p.first][p.second + 1] = p.second + 1;
	}

	// check
	int cnt = 0;
	for (int i = 0; i < N; ++i)
	{
		int cur = i;
		for (int k = 0; k < H; ++k)
		{
			if (vertical[k][cur] != 0)
			{
				cur = vertical[k][cur] - 1;
			}
		}
		if (i == cur)
		{
			cnt++;
		}
	}
	if (cnt == N)
	{
		cout << num;
		isDone = true;
		exit(0);
		return;
	}
}
 
void makePermutation(vector<vector<int>> vertical, vector<pair<int, int>> parti, vector<pair<int, int>> permu, int n, int r, int depth)
{
	if (r == depth)
	{
        cnt2++;
		check(vertical, permu);
        cout << cnt2 << "\n";
		return;
	}

	for (int i = depth; i < n; ++i)
	{
		if (permu.size())
		{
			if (permu.back().first == parti[i].first && permu.back().second == parti[i].second - 1)
				continue;
		}        
		permu.push_back(parti[i]);
		makePermutation(vertical, parti, permu, n, r, depth + 1);
		permu.pop_back();
	}

}

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

	if (M == 0) {
		cout << 0; return 0;
	}

	vector<vector<int>> vertical(H, vector<int>(N, 0));
	for (int i = 0; i < M; ++i)
	{
		cin >> a >> b;
		a--; b--;
		vertical[a][b] = b + 2;
		vertical[a][b + 1] = b + 1;
	}

	vector<pair<int, int>> parti, permu;
	for (int r = 0; r < H; ++r)
	{
		for (int c = 0; c < N - 1; ++c)
		{
			if (vertical[r][c] == 0 && vertical[r][c + 1] == 0)
				parti.push_back({ r,c });
		}
	}

	for (int num = 0; num < 4; ++num)
	{
		makePermutation(vertical, parti, permu, parti.size(), num, 0);
	}

	if (!isDone)
		cout << -1;

	return 0;
}

이렇게 하고

5 5 6
1 1
3 2
2 3
5 1
5 4

입력시

663번 호출됩니다.

반면 제 코드는 199번 호출 됩니다.

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int n, m, h, a, b, ret = INF, visited[34][34];
int cnt2 = 0;
bool check(){
    cnt2++;
    cout << cnt2 << "\n";
    for(int i = 1; i <= n; i++){
        int start = i;
        for(int j = 1; j <= h; j++){
            if(visited[j][start])start++;
            else if(visited[j][start - 1])start--;
        }
        if(start != i) return false;
    }
    return true;
}
void go(int here, int cnt){ 
    if(cnt > 3 || cnt >= ret) return;
    if(check()){
        ret = min(ret, cnt); return;
    }
    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;
        }
    }
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> h;
    for(int i = 0; i < m; i++){
        cin >> a >> b; visited[a][b] = 1;
    }
    go(1, 0);
    cout << ((ret == INF) ? -1 : ret) << "\n";
	return 0;
}

또한 수강생님 코드는 이해했습니다.

0, 1, 2 개에 따른 조합부터 해서 일종의 백트래킹을 구현하신 것이죠.

그러나.

제 코드가 수강생님 코드보다 무조건 더 함수호출을 많이 안하냐?

그런 것은 또 아닙니다.

5 8 6
1 1
2 2
3 3
4 4
3 1
4 2
5 3
6 4

이런 예제의 경우 수강생님 코드가 더 함수호출을 적게 합니다.

제 생각에는 2가지 이유때문에 이 코드가 시간초과가 뜨는 것 같습니다.

1. 문제를 출제 할 때 보통은 해설코드를 정해놓고 출제를 합니다.

즉, 아 이 문제를 백트래킹으로 출제를 해야겠다고 생각하면 보통은 백트래킹 코드를 구현 -> 해당 해설 코드에 맞는 적절한 TC를 구축해서 문제를 출제하게 됩니다.

제 생각에는 private TC 자체가 백트래킹 - DFS 에 맞춰져 있는 것같습니다.

어떠한 입력이 있는데 그부분은 수강생님 코드가 함수호출을 더 많이 해서 -> 시간초과가 되는 것이죠.

2. 중복되는 로직이 존재합니다. 예를 들어 0 1 의 사다리를 놓는다. nC2 이후에 다시 0 1 2 의 사다리를 놓고 다시 계산하게 됩니다.

만약 dfs로 할 경우에는 0 1 check 이어서 0 1 2 이렇게 check가 가능합니다.

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

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

감사합니다.

강사 큰돌 올림.

maruche님 다시 답변 달았습니다. 참고 부탁드립니다.

정성스런 답변 감사합니다.... 덕분에 원인을 이해할 수 있는 것 같습니다.

다시 반론을 제기하게 되어 정말 죄송스럽습니다만,, 말씀해주신 "제 코드가 예시코드(강사님 코드)보다 더 많은 함수 호출을 하게 되는 경우" 의 예시로 들어주신 문제의 예제입력 3번

5 5 6
1 1
3 2
2 3
5 1
5 4

은 뭔가 착오가 있으신 것 같습니다. 아래는 제 코드와 강사님의 코드를 모아두고 각각 cnt2, cnt3를 계산한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int n, m, h, a, b, ret = INF, visited[34][34];
int cnt2 = 0;
int cnt3 = 0;
bool isDone = false;

bool check() {
    cnt3++;
    for (int i = 1; i <= n; i++) {
        int start = i;
        for (int j = 1; j <= h; j++) {
            if (visited[j][start])start++;
            else if (visited[j][start - 1])start--;
        }
        if (start != i) return false;
    }
    return true;
}
void go(int here, int cnt) {
    if (cnt > 3 || cnt >= ret) return;
    if (check()) {
        ret = min(ret, cnt); return;
    }
    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;
            cout << i << "," << j << " " ;
            go(i, cnt + 1);
            cout << endl;
            visited[i][j] = 0;
        }
    }
}


void check2(vector<vector<int>> vertical, vector<pair<int, int>> parti)
{
    int num = parti.size();

    // add
    for (int it = 0; it < num; ++it)
    {
        pair<int, int> p = parti[it];
        vertical[p.first][p.second] = p.second + 2;
        vertical[p.first][p.second + 1] = p.second + 1;
    }

    // check
    int cnt = 0;
    for (int i = 0; i < n; ++i)
    {
        int cur = i;
        for (int k = 0; k < h; ++k)
        {
            if (vertical[k][cur] != 0)
            {
                cur = vertical[k][cur] - 1;
            }
        }
        if (i == cur)
            cnt++;
    }
    if (cnt == n)
    {
        cout << num;
        isDone = true;
        cout << "\n내코드 " << cnt2 << endl;
        exit(0);
        return;
    }

}

void makeCombi(vector<vector<int>> vertical, vector<pair<int, int>> parti, vector<pair<int, int>> permu, int n, int r, int depth)
{
    if (r == permu.size())
    {
        cnt2++;
        check2(vertical, permu);
        return;
    }

    for (int i = depth + 1; i < n; ++i)
    {
        if (permu.size())
        {
            if (permu.back().first == parti[i].first && permu.back().second == parti[i].second - 1)
                continue;            
        }

        permu.push_back(parti[i]);
        makeCombi(vertical, parti, permu, n, r, i);
        permu.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> h;

    vector<vector<int>> vertical(h, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        visited[a][b] = 1;
        //---------------
        a--; b--;
        vertical[a][b] = b + 2;
        vertical[a][b + 1] = b + 1;

    }
    go(1, 0);
    cout << ((ret == INF) ? -1 : ret) << "\n";
    cout << "예제코드 " << cnt3 << endl;


    //---------------
    vector<pair<int, int>> parti, permu;
    for (int r = 0; r < h; ++r)
    {
        for (int c = 0; c < n - 1; ++c)
        {
            if (vertical[r][c] == 0 && vertical[r][c + 1] == 0)
                parti.push_back({ r,c });
        }
    }
    for (int num = 0; num < 4; ++num)
    {
        makeCombi(vertical, parti, permu, parti.size(), num, -1);
    }

    if (!isDone)
        cout << -1 << endl;
    cout << "내코드 " << cnt2 << endl;


    return 0;
}

위의 예제 3번을 입력한 결과

예제코드는 말씀하신대로 199번, 제 코드는 83번 호출이 됐습니다. 디버깅 찍어가면서 확인도 해봤는데요, 우선 해당 예제에서는 다음과 같이 12개의 사다리가 놓일 수 있는 후보군이 존재합니다. 빨간 형광펜이 후보군, 파란색 o-o형태가 문제에서 제시된 사다리입니다.

12C0=1

12C1=12

12C2-7=66-7=59 (-7은 사다리를 나란히 세울 수 있는 경우의 수 입니다. 1행에서 1개, 4행과 6행에서 각 3개의 경우의 수가 존재합니다.)

이렇게 3개의 사다리를 뽑기 이전까지 총 72번의 호출이 됩니다. 그 이후 3개를 체크하면서 정답이 되면 exit(0)을 호출하여 제 코드는 총 83번의 호출이 필요했습니다.

이 외의 다른 모든 예제에서도 제 코드가 함수 호출 횟수가 적었습니다만, 말씀해주신 특화된 private TC를 생각해봤습니다. 사다리를 놓을 수 있는 위치를 배열로 갖고 있을 때 v[0], v[1], v[2]가 정답일 경우엔,, 아마 강사님의 코드는 0, 01, 012로 정답을 찾고 이후에 1개와 2개를 탐색을 하겠죠. 그리고 제 코드는 nC1, nC2를 다 탐색한 후 nC3의 첫 원소인 정답을 찾을 것 입니다.

이런 경우에도 함수 호출에서 의미있는 차이는 찾기 힘들 것 같다는 결론이 나왔습니다. v[0], v[1], v[2]가 아니더라도.. 036 이더라도 강사님의 코드는 035까지의 모든 3개인 경우를 다 순회할 것이며 이는 제 코드 또한 동일합니다. 아무리 생각하고 반례를 입력해봐도 제 코드에서 호출이 의미있게 튀는 경우는 없었습니다. 총 경우의 수 역시 1+270C1+270C2+270C3로 약 300만 대의 횟수인데 말이죠..

// 애초에 반례를 만들기가 상당히 어렵더군요;; 012가 정답인 사다리를 만드려고 노력했으나 맘대로 되진 않고 겨우 만든게 정답이 025인 반례였는데 이 역시도 함수 호출 횟수는 비슷했습니다. (예제19, 제코드16)
5 9 6
1 2
1 4
2 1
2 3
3 2
3 4
4 2
4 4
5 3

긴 글 읽어주셔서 감사합니다..

안녕하세요 ㅎㅎ

이런 경우에도 함수 호출에서 의미있는 차이는 찾기 힘들 것 같다는 결론이 나왔습니다. v[0], v[1], v[2]가 아니더라도.. 036 이더라도 강사님의 코드는 035까지의 모든 3개인 경우를 다 순회할 것이며 이는 제 코드 또한 동일합니다. 아무리 생각하고 반례를 입력해봐도 제 코드에서 호출이 의미있게 튀는 경우는 없었습니다. 총 경우의 수 역시 1+270C1+270C2+270C3로 약 300만 대의 횟수인데 말이죠..

>> 음.. 어느정도는 동의하지만 생각해보면

수강생님의 코드는

사다리 한개씩 들어간다 -> 사다리 2개씩 들어간다 -> 3개씩 들어간다 인데

처음에 사다리 3개를 그냥 넣었을 때 되는 경우를 생각한다면 사실 그부분에서 함수호출은 더 많이 하는 것은 자명하니까요.

해당 부분에 있어 더 많은 함수 호출이 일어나는 반례는 존재할 수 있다 생각합니다.

예제3번.

...

예제코드는 말씀하신대로 199번, 제 코드는 83번 호출이 됐습니다.

>> 해당 부분은 확인했습니다.

제가 틀리게 말씀 드렸네요.. 지금 다시 해보니까 663이 안 나오네요..

혼란을 드려 죄송합니다. ㅠㅠ

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

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

감사합니다.

강사 큰돌 올림.

조금 더 보강을 드리면요. 이런 그림을 생각하시면 됩니다.

수강생님 코드는 4번. 아래의 경우는 2번이면 끝나니까요.

(아래의 그림같은 경우 밑의 가지가 많아도 DFS처럼 쭉 들어갔을 때를 생각하시면 됩니다.)