5-M_12100_2048(Easy)

Question

안녕하세요 큰돌님! go 재귀 함수에 대해 이해가 되지 않는 부분이 있습니다. 제가 완탐에 대한 이해가 부족해서 함수 호출에 대한 로직이 이해가 안되는 것 같습니다. 질문 Board d = c; 로 원본과 동일한 보드를 생성하고 d._move()하는 것 까지는 이해를 했습니다. 그런데 그 다음에 왜 d._rotate90();가 아닌 c._rotate90();를 하는지 모르겠습니다. move한 다음 rotate, 또 다시 move한 다음 rotate 과정을 반복하려면 d._rotate90();가 되어야하는 것 아닌가요..? d._move(); go(d, here + 1); c._rotate90(); 이 과정만으로 5번 이동시키는 완탐을 진행할 수 있는지 이해가 안됩니다 ㅜㅜ 혹시 함수 호출이 어떻게 진행되는지 그림으로 설명해주실 수 있나요? 제가 생각한 완탐 방식은 아래와 같습니다. 함수 호출 순서가 go(d, here + 1); c._rotate90(); 인데 그러면 마지막 호출되는 함수가 return 되고 rotate과정이 진행되는게 아닌가요? rotate함수가 언제 실행되는지 잘 모르겠습니다. 제가 생각하는 함수 호출 순서는 아래 그림과 같습니다. 뭔가 그림이 카오스네요.. 큰돌님 코드 void go(Board c, int here){ if(here == 5){ c.get_max(); return; } for(int i = 0; i < 4; i++){ Board d = c; // 동일한 구조체 생성 d._move(); go(d, here + 1); c._rotate90(); } return; }

큰돌 · Answer

안녕하세요 효민님 ㅎㅎ 그림그리시면서 잘 공부하고 계시네요 ㅎㅎ 그 다음에 왜 d._rotate90();가 아닌 c._rotate90();를 하는지 모르겠습니다.   >> 일단 d와 c에 대해서 설명하자면요. c는 매개변수로 넘겨받은 board입니다. d는 그 c를 기반으로 할당한 board고 이걸 기반으로 move()를 하고 다시 재귀함수 go를 호출합니다.   우리가 해야 할일은. 4가지의 경우의 수를 판단해야 합니다.   사각형 하나를 왼쪽으로 미는 작업 사각형 하나를 90도 회전후 왼쪽으로   사각형 하나를 90도 * 2 회전후 왼쪽으로   사각형 하나를 90도 * 3 회전후 왼쪽으로 이렇게 하면 모든 경우의 수를 판단할 수 있죠? 이걸 코드로 어떻게 구현해야할까요? 일단은..   사각형 하나를 왼쪽으로 미는 작업   이거는 쉽죠? 단순하게 void go(Board c, int here){ c._move(); go(c, here + 1); 이렇게 해도 될겁니다. 자 근데... 2.사각형 하나를 90도 회전후 왼쪽으로   이게 문제인데요. 이거를 1번을 한 후에 하려면 어떻게 해야하죠? 원복이 필요합니다. 1번의 상태값이 move()를 한 이후에 다시 그 상태값으로 하면... 제대로 된 원복이 아니죠. 1 -> a, b, c, d 이렇게 되어야 하는데 1 -> a -> b ... 이렇게 되어버리는 것이죠. 자 그러면 이런코드가 필요할 겁니다. void go(Board c, int here){ c._move(); go(c, here + 1); c._notmove(); c.rotate(); c._move(); go(c, here + 1); 이거를 좀 더 효율적으로 표현하자면.. Board d = c; d._move(); go(d, here + 1); c._rotate90(); Board d = c; d._move(); go(d, here + 1); c._rotate90(); 이렇게 되는 것이죠. d라는 것을 이용해서 notmove를 할 필요없게 만듭니다. (어차피 받아온 매개변수 상태로만 만들면 되기 때문에) 그걸 이용한 후 move를 하고 넘기는 것이죠. 그 담에 rotate를 걸구요. 이를 좀 더 효율적으로 만들면 for(int i = 0; i < 4; i++){ Board d = c; d._move(); go(d, here + 1); c._rotate90(); } 이렇게 되는 것입니다.   혹시 함수 호출이 어떻게 진행되는지 그림으로 설명해주실 수 있나요? >> 제가 지금 태블릿이 없는 상황이라 그림은 좀 힘들어욤 ㅠㅠ 양해부탁드립니다.   다만... 저거 근데 효민님이 그리신 그림이 맞습니다. 1,2번 경우의 수 말씀하신 것 다 맞습니다. rotate 한번 없이 계속 move한 경우의 수도 나타날 수 있습니다.     go(d, here + 1); c._rotate90(); 인데 그러면 마지막 호출되는 함수가 return 되고 rotate과정이 진행되는게 아닌가요? rotate함수가 언제 실행되는지 잘 모르겠습니다. >> 이렇게 보시면 됩니다. 쉽게 최대 2번이라고 가정하고 move를 m, rotate90를 r이라고 했을 때 mm m r m m r r m m r r r m r m m .... 이런식으로 되는 것이죠. 설명하신 그림 자체가 맞습니다. 잘 그리셨어요.. ㅋㅋ 인데 그러면 마지막 호출되는 함수가 return 되고 rotate과정이 진행되는게 아닌가요? rotate함수가 언제 실행되는지 잘 모르겠습니다. >> 맞아요. move 다 하고... 마지막에 mmmrm 이런식으로 진행됩니다. 처음 등장하는 경우의 수는 move만 많이 한 경우의 수가 됩니다.   감사합니다.