백준 6603 로또(bfs)

https://jaimemin.tistory.com/579

백준 6603번 로또

먼저, 이 코드는 위에 적어놓은 블로그의 코드를 거의 배끼다 싶이했다.

그럼에도 불구하고, 블로그에 기록하는 이유는 재귀를 따라가보면서 하나하나 기록해놓으면 지금이나 나중에 재귀를 공부할 때 큰 도움이 될거라 생각했다.

나는 문제를 보고 도무지 못 풀겠다 싶으면 저 블로그에 검색해본다. 내 생각이지만 정말 코드를 잘 짜시는 것 같다. 굉장히 직관적(?)으로 코드를 짜셔서 초보인 나도 이해하기가 편하다.

 

#include <iostream>

 

using namespace std;

 

const int MAX = 6;

int lotto[MAX];

int arr[13];

int k;

 

void makeLotto(int start, int end)

{

    if (end == MAX)

    {

        for (int i = 0; i < MAX; i++)

            cout << lotto[i] << " ";

        cout << "\n";

        return;

    }

    for (int i = start; i < k; i++)

    {

        lotto[end] = arr[i];

        makeLotto(i + 1, end + 1);

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(NULL);

    while (1)

    {

        cin >> k;

        if (k == 0)

            break;

        for (int i = 0; i < k; i++)

            cin >> arr[i];

        makeLotto(0, 0);

        cout << "\n";

    }

    return 0;

}

 

7 1 2 3 4 5 6 7 이라는 input이 들어왔을 때의 재귀를 따라가 보겠다!!

tail recursion이 아니기 때문에 나머지 부분은 stack에 저장하게 된다. 이는 stack(n)으로 표현하겠다!

---------------------------------------------------------------------------------------------------------

makeLotto(0,0)호출  i=0일 때  lotto[0] = arr[0] 

 

stack(0)에는  for (int i = start(0을 처리했으므로 현재 start는 1); i < k; i++)

                 {

                     lotto[0] = arr[i];

                 }

 

현재 lotto=[1]

---------------------------------------------------------------------------------------------------------

makeLotto(1,1)호출  i=1일 때  lotto[1] = arr[1]

 

stack(1)에는  for (int i = start(1을 처리했으므로 현재 start는 2); i < k; i++)

                 {

                     lotto[1] = arr[i];

                 }

 

현재 lotto=[1, 2]

----------------------------------------------------------------------------------------------------------

makeLotto(2,2)호출  i=2일 때  lotto[2] = arr[2]

 

stack(2)에는  for (int i = start(2을 처리했으므로 현재 start는 3); i < k; i++)

                 {

                     lotto[2] = arr[i];

                 }

 

현재 lotto=[1, 2, 3]

----------------------------------------------------------------------------------------------------------

makeLotto(3,3)호출  i=3일때  lotto[3] = arr[3]

 

stack(3)에는  for (int i = start(3을 처리했으므로 현재 start는 4); i < k; i++)

                 {

                     lotto[3] = arr[i];

                 }

 

현재 lotto=[1, 2, 3, 4]

-----------------------------------------------------------------------------------------------------------

makeLotto(4,4)호출  i=4일때  lotto[4] = arr[4]

 

stack(4)에는  for (int i = start(4을 처리했으므로 현재 start는 5); i < k; i++)

                 {

                     lotto[4] = arr[i];

                 }

 

현재 lotto=[1, 2, 3, 4, 5]

------------------------------------------------------------------------------------------------------------

makeLotto(5,5)호출  i=5일때  lotto[5] = arr[5]

 

stack(5)에는  for (int i = start(5을 처리했으므로 현재 start는 6); i < k; i++)

                 {

                     lotto[5] = arr[i];

                 }

 

현재 lotto=[1, 2 , 3, 4, 5, 6]

--------------------------------------------------------------------------------------------------------------

make(6,6)호출

end가 6이므로 lotto 배열을 출력하고 return!

따라서 stack의 가장 위 stack(5)를 가져온다.(여기서부터는 for loop를 조금 더 구체적으로 적는다.

 

for (int i = start(5을 처리했으므로 현재 start는 6); i < k; i++)

{

    lotto[5] = arr[i];

    makeLotto(i + 1, end + 1);      //start=5, end=5인 상태

}

 

i=6인 경우

lotto[5] = arr[6]   =>  현재 lotto=[1,2,3,4,5,7]

-------------------------------------------------------------------------------------------------------------

makeLotto(7,6) 호출

end가 6이므로 lotto 배열을 출력하고 return!

 

stack(5)는 for loop가 다 돌아감!(k=7이기 때문에)

 

따라서 stack의 가장 위 stack(4)를 가져온다.

 

for (int i = start(4을 처리했으므로 현재 start는 5); i < k; i++)

{

    lotto[4] = arr[i];

    makeLotto(i + 1, end + 1);  //start=4, end=4인 상태

}

 

i=5인 경우 

lotto[4] = arr[5]  =>  현재 lotto=[1,2,3,4,6,7]

--------------------------------------------------------------------------------------------------------

makeLotto(6,5) 호출

 

    for (int i = 6; i < k; i++)

    {

        lotto[5] = arr[i];

        makeLotto(i + 1, end + 1);

    }

 

lotto[5]=arr[6]  => 현재 lotto=[1,2,3,4,6,7]

------------------------------------------------------------------------------------------------------

makeLotto(7,6) 호출

end가 6이므로 lotto 배열을 출력하고 return!

 

stack(4)는 끝났으므로 stack(3)을 가져온다.

 

 for (int i = start(3을 처리했으므로 현재 start는 4); i < k; i++)

 {

   lotto[3] = arr[i];  //start=3, end=3

   makeLotto(i + 1, end + 1);

 }

 

lotto[3]=arr[4]  => 현재 lotto=[1,2,3,5,6,7]

--------------------------------------------------------------------------------------------------------

makeLotto(5,4) 호출

 

 for (int i = 5; i < k; i++)

 {

   lotto[4] = arr[i];  

   makeLotto(i + 1, end + 1);

 }

 

i=5일 때 

lotto[4]=arr[5]  =>현재 lotto=[1,2,3,5,6,7]

--------------------------------------------------------------------------------------------------------

makeLotto(6,5) 호출

 

for (int i = 6; i < k; i++)

 {

   lotto[5] = arr[i];  

   makeLotto(i + 1, end + 1);

 }

 

i=6일 때 

lotto[5]=arr[6]  =>현재 lotto=[1,2,3,5,6,7]

 

출력!

 

.............

 

이렇게 i와 end를 1씩 같이 증가시키면 stack frame에 의해 배열의 한 칸씩 앞으로 오면서 그 값을 바꿔자나지만, 이미 지나온 배열의 값은 변하게 하지 않는다.

 

재귀를 사용하고 이해하는 것은 너무나도 어렵다. 하지만 이런 큰 틀을 외우고 있으면 비슷한 재귀 문제를 간단히 풀 수 있게 될 것 같기도 하다. 굳이 시간을 들여 재귀를 따라간 이유는 이렇게 한번 해보면 그 흐름이 조금은 이해가 가는 기분이 들어 따라가봤다. 많은 재귀 문제들을 풀어보면서 익숙해지는 것이 중요하지 않을까 싶다.