문제

풀이 과정

백트래킹 - dfs를 이용하였다.

전체적인 아이디어는 다음과 같다.

일단 트리의 왼쪽으로 끝까지 내려 간 후 백트래킹. 즉 위로 한칸씩 올라오며 원소를 빼고 넣고를 반복한다.

즉 1-2-3-4-5-6-7이라 한다면

1-2-3-4-5-6, 1-2-3-4-5-7, 1-2-3-4-6-7 이런식으로 진행 되는 것이다.

나는 backtracking 이라는 함수를 만들어 호출하였다. (사실 지난 학기 알고리즘 시간에 배운 원리를 그대로 적용하였다.)

코드

// bj6603.cpp: 콘솔 응용 프로그램의 진입점을 정의합니다.
//

#include "stdafx.h"
#include <iostream>
using namespace std;

void backtracking(int *arry,int *arr,int arrnum2, int k, int l) {

    if (arry[5] != 0) {
        for (int i = 0; i < 6; i++)
            cout << arry[i] << " ";
        cout << endl;

    }

    if (arry[0] < arr[arrnum2 - 5] && k<arrnum2  && arry[5] == 0 ) {
        arry[l] = arr[k];
        backtracking(arry,arr, arrnum2, k+1, l+1);
        arry[l] = 0;
        backtracking(arry,arr, arrnum2, k+1,l);
    }
}

int main()
{
    int a[5][3] = {0,};
    int x[10] = { 0, };
    int arr[10][13] = {0,};
    int arry[6] = {0,};
    int arrnum[10];
    int row=0, col=0;
    int input;
    int i,j=0;
    cin >> input;
    arrnum[0] = input;
    for (i = 0; i < input; i++)
        cin >> arr[0][i];
    while (getchar() == '\n') {
        row++;
        cin >> input;
        arrnum[row] = input;
        if (input == 0) {
        //    cout << "end";
            break;

        }
        else {
            for (i = 0; i < input; i++) {
                cin >> arr[row][i];
            }
        }
    }
    row = 0;

    while (arr[row][0] != 0) {
        int k = 0;
        int l = 0;
        int n = arrnum[row];
        int arry[6] = { 0, };
        backtracking(arry,arr[row], n, k, l);
        row++;
        cout << endl;
    }

    return 0;
}

시행착오

처리되지 않은 예외.stack overflow의 발생

위와 같은 문구가 뜨는 경우는 backtracking 시 너무 깊이 들어가서 이다. 조건에 맞추어 재귀함수를 호출하는 부분에서 조건을 잘못 설정 하여 재귀 함수가 끊임없이 호출되는 경우 이다. 이런 경우 스택이 가득 차게 되어 에러가 난다. 따라서 재귀 함수를 호출할 조건을 신중히 다시 살펴보자. 또한 이런 경우 디버깅 시 F10으로 보면 보이지 않으니 F11을 눌러가며 디버깅 할 수 있도록 하자.