데브림의 블로그 포스팅 한 것들을 한 눈에 확인하고 싶다면 클릭!
👉 https://github.com/DevLimK1/tistory-map 👈
🤔포스팅을 통해 얻어갈 수 있는 지식🧐
✔ 재귀에 대해 이해를 할 수 있다.
✔ 하노이 탑 코드를 이해를 할 수 있다.
새벽시간에 하노이 탑을 이해하여 빠르게 독자분들에게 지식을 공유하기 위해서 작성하게 되었다..
나와 같이 하노이 탑을 이해하는데 오랜시간들인 독자분들도 하노이탑 코드를 이해할 수 있기를 바라며...
먼저 직관적으로 코드를 통해서 어떻게 동작하는지 이해해본 후에 예시를 통해서 더 자세하게 살펴보는 것이 이해하는데 더 도움이 될 거 같다.
1: public class 하노이탑 {
2: public static void main(String[] args) {
3: Scanner scanner=new Scanner(System.in);
4: int num; //원판 갯수
5: num=scanner.nextInt();
6: hanoi(1,2,3,num);
7: }
8:
9: public static void hanoi(int from,int m,int to,int num){//from -> to 로 원판num이 이동
10: if(num==0)
11: return;
12: hanoi(from,to,m,num-1); // 원판num-1은 from -> m으로 이동
13: System.out.printf("%d : %d -> %d\n",num,from,to);//원판num이 from -> to 이동
14: hanoi(m,from,to,num-1); // 원판num-1이 m -> to로 이동
15: }
16: }
17: 😀 여기서 중요하게 이해하여야 할 코드부분은, 13: 번째 줄이다. 왜냐하면, System.out.printf 부분이 실행되면 실제로 원판 하나가 움직였다고 생각해야 한다.(위 코드에서는 원판 번호가 num인 것이 from->to로 이동)
하노이 탑을 이해할 때는 코드 전체적인 흐름을 이해하고 세부사항으로 좁혀서 이해하는 것이 핵심인데, 필자는 지금까지 하노이 탑을 이해할 때 너무 세부적인 코드 한 줄 한 줄 이해하려다 보니 핵심을 파악하지 못했던 거 같다.
자, 다시 한번 강조하지만 System.out.printf 부분이 실행되면 실제로 원판 하나가 움직였다고 생각해야 한다.
😀 9: public static void hanoi(int from,int m,int to,int num){//from -> to 로 원판num이 이동
위의 예시는 원판이 2개인데, 코드를 직관적으로 이해하기 위해서 변수명을 그대로 사용했다.
위에서 강조했듯이, System.out.printf가 실행되어야 실제로 원판이 움직이는 것이다.
"원판num은 from->to로 이동을 해야하는 구나" 정도로 이해하고 다음 코드로 넘어가야 한다.
😀 12: hanoi(from,to,m,num-1); // 원판num-1은 from->m으로 이동
원판num이 from->to로 이동하기 위해서는 먼저 위에 있는 원판num-1이 from -> m으로 이동을 해야한다.
위 함수는 재귀함수로, 원판num-1이 m으로 이동하는 System.out.printf 가 먼저 실행 될 것이다.
그래서 원판num-1은 m으로 이동시킨다.(실제로 이동한 원판은 노랑색으로 색칠하겠다.)
😀 13: System.out.printf("%d : %d -> %d\n",num,from,to);//원판num이 from -> to 이동
System.out.printf 가 실행되었음으로 실제 원판num이 목적지 to로 이동한다.
😀 14: hanoi(m,from,to,num-1); // 원판num-1이 m->to로 이동
재귀함수(메서드)가 실행된다. 지금 예시에서는 원판num-1이 m->to로 이동하는 것을 알 수 있다.
9: public static void hanoi(int from,int m,int to,int num){//from -> to 로 원판num이 이동
12: hanoi(from,to,m,num-1); // 원판num-1은 from -> m으로 이동
13: System.out.printf("%d : %d -> %d\n",num,from,to);//원판num이 from -> to 이동
14: hanoi(m,from,to,num-1); // 원판num-1이 m -> to로 이동
15:}
😀 자, 코드의 흐름을 주석이 써져있는대로 읽어보도록 하겠다.
9: from -> to로 원판num을 이동시키는 것이 목표! (실제 원판 이동x)
12: 재귀메서드를 호출하게되면 위의 예시에서는 원판num-1이 from->m으로 먼저 이동을한다(실제 원판 이동 O)
13: 원판num이 from->to로 이동한다.(실제 원판이동O) : 메서드 실행할 때 목표 달성!
14: 원판num-1이 m->to로 이동(실제 원판이동O)
실제 원판이동한 것을 나타내면
12:원판num-1이 from -> m 이동
13:원판num이 from->to로 이동
14:원판num-1이 m->to로 이동
12번째,14번째 줄은 원판num 위에 있던 원판num-1이 경유지 m으로 이동했다가 목적지 to로 이동하는 것을 알 수 있다.
원판이 3개일 때
✔ num=3일 때)
1: public class 하노이탑 {
2: public static void main(String[] args) {
3: Scanner scanner=new Scanner(System.in);
4: int num; //원판 갯수
5: num=scanner.nextInt();
6: hanoi(1,2,3,3);
7: }
8:
9: public static void hanoi(int from,int m,int to,int num){//from(1) -> to(3) 로 원판3이 이동
//from:1 m:2 to:3 num:3
10: if(num==0)
11: return;
12: hanoi(from,to,m,num-1); // 원판2가 from(1) -> m(2)으로 이동
//from:1 to:3 m:2 num-1:2
13: System.out.printf("%d : %d -> %d\n",num,from,to);//실제 원판3이 from(1) -> to(3) 이동
//num:3 from:1 to:3
14: hanoi(m,from,to,num-1); // 원판2가 m(2) -> to(3)로 이동
//m:2 from:1 to:3 num-1:2
15: }
16: }
17: 
😀
9: public static void hanoi(int from,int m,int to,int num){//from(1) -> to(3) 로 원판3이 이동
//from:1 m:2 to:3 num:3
12: hanoi(from,to,m,num-1); // 원판2가 from(1) -> m(2)으로 이동
//from:1 to:3 m:2 num-1:2
원판3이 from-> to로 이동하기 위해서는 원판2가 먼저 m(2)으로 이동해야 할 것이다.
재귀메서드를 호출해서 타고 들어가보자.
✔ num=2 일 때)
9: public static void hanoi(int from,int m,int to,int num){//from(1) -> to(2) 로 원판2이 이동
//from:1 m:3 to:2 num:2
10: if(num==0)
11: return;
12: hanoi(from,to,m,num-1); // 원판1이 from(1) -> m(3)으로 이동
//from:1 to:2 m:3 num-1:1
13: System.out.printf("%d : %d -> %d\n",num,from,to);//실제 원판2가 from(1) -> to(2) 이동
//num:2 from:1 to:2
14: hanoi(m,from,to,num-1); // 원판1이 m(3) -> to(2)로 이동
//m:3 to:2 num-1:1
15: }
😀
9: public static void hanoi(int from,int m,int to,int num){//from(1) -> to(2) 로 원판2이 이동
//from:1 m:3 to:2 num:2
12: hanoi(from,to,m,num-1); // 원판1이 from(1) -> m(3)으로 이동
//from:1 to:2 m:3 num-1:1
여기서 많이 헷갈려하는게 from -> to로 원판2가 이동해야하는데 왜 m 으로 이동하는거지? 라고 생각하는 경우다. 이전에 재귀메서드로 호출 받았음을 기억해야한다.
num=3일 때 12: hanoi(from,to,m,num-1); // 원판2가 from -> m으로 이동
//from:1 to:3 m:2 num-1:2
위의 식을 호출하게 되면
9: public static void hanoi(int from,int m,int to,int num){//from -> to 로 원판2이 이동
//from:1 m:3 to:2 num:2
목적지 to가 (2)가 된다.
그런데, 원판2가 (2)로 이동하기 위해서는 그 위에 있는 원판1이 (3)으로 이동을 해야한다.
그래서 아래 재귀메서드가 또 호출되는 것이다.
12: hanoi(from,to,m,num-1); // 원판1이 from -> m으로 이동
//from:1 to:2 m:3 num-1:1
★ 참고로, 실제로 이동된 원판은 없다! System.out.printf 가 실행되어야 실제 원판이 이동하는 것!
✔ num=1 일 때)
9: public static void hanoi(int from,int m,int to,int num){//from(1) -> to(3) 로 원판1이 이동
//from:1 m:2 to:3 num:1
10: if(num==0)
11: return;
12: hanoi(from,to,m,num-1); // 원판0이 from(1) -> m(2)으로 이동
//from:1 to:3 m:2 num-1:0
13: System.out.printf("%d : %d -> %d\n",num,from,to);//실제 원판1이 from(1) -> to(3) 이동
//num:1 from:1 to:3
14: hanoi(m,from,to,num-1); // 원판0이 m(2) -> to(3)로 이동
//m:2 to:3 num-1:0
15: }
😀 9: public static void hanoi(int from,int m,int to,int num){//from(1) -> to(3) 로 원판1이 이동
//from:1 m:2 to:3 num:1
10: if(num==0)
11: return;
12: hanoi(from,to,m,num-1); // 원판0이 from(1) -> m(2)으로 이동
//from:1 to:3 m:2 num-1:0
13: System.out.printf("%d : %d -> %d\n",num,from,to);//원판1이 from(1) -> to(3) 이동
//num:1 from:1 to:3
14: hanoi(m,from,to,num-1); // 원판0이 m(2) -> to(3)로 이동
//m:2 to:3 num-1:0
12: 에서 원판0은 존재하지 않음으로 메서드 호출하면 결국 10: 11: return; 하게 되고
13:이 실행되어 실제로 원판1이 from(1) -> to(3) 이동하게 된다. (노란색 색칠)
14: 코드도 원판0이 존재하지 않음으로 메서드 호출해봤자 return; 하게 된다.
✔ num=2 일 때)
9: public static void hanoi(int from,int m,int to,int num){//from(1) -> to(2) 로 원판2이 이동
//from:1 m:3 to:2 num:2
10: if(num==0)
11: return;
12: hanoi(from,to,m,num-1); // 원판1이 from(1) -> m(3)으로 이동
//from:1 to:2 m:3 num-1:1
13: System.out.printf("%d : %d -> %d\n",num,from,to);//실제 원판2가 from(1) -> to(2) 이동
//num:2 from:1 to:2
14: hanoi(m,from,to,num-1); // 원판1이 m(3) -> to(2)로 이동
//m:3 to:2 num-1:1
15: }😀
12: 재귀 호출 했었던 메서드가 리턴 받고
13: 코드가 실행되면서 실제 원판 2가 from(1) ->to(2)로 이동하게 된다.
14: 원판3이 (3)으로 이동하기 위해서는 (3)에 있는 원판1이 (2)로 이동해야한다.
✔ num=1 일 때)
9: public static void hanoi(int from,int m,int to,int num){//from(3) -> to(2) 로 원판1이 이동
//from:3 m:1 to:2 num:2
10: if(num==0)
11: return;
12: hanoi(from,to,m,num-1); // 원판0이 from(3) -> m(1)으로 이동
//from:3 to:2 m:1 num-1:0
13: System.out.printf("%d : %d -> %d\n",num,from,to);//실제 원판1이 from(3) -> to(2) 이동
//num:1 from:3 to:2
14: hanoi(m,from,to,num-1); // 원판0이 m(1) -> to(3)로 이동
//m:1 to:2 from:3 num-1:1
15: }😀 이제는 코드를 보면서 이해할 수 있을 것이다.
원판1이 (3) 에서 (2)로 이동하고
나머지 코드들은 원판0이 실행되는 코드이기 때문에 원판0은 존재하지않음으로 return되어 메서드가 종료하게 된다.
그럼 다시 위의 num=2일 때 14: 번째 줄의 코드로 return이 되면서 num=2일 떄 메서드도 종료하게 된다. 그래서 num=3일 때의 메서드가 실행되는데 같이 살펴보도록 하자. (이제 끝이 얼마 안남았다..!!)
✔ num=3 일 때)
9: public static void hanoi(int from,int m,int to,int num){//from(1) -> to(3) 로 원판3이 이동
//from:1 m:2 to:3 num:3
10: if(num==0)
11: return;
12: hanoi(from,to,m,num-1); // 원판2가 from(1) -> m(2)으로 이동
//from:1 to:3 m:2 num-1:2
13: System.out.printf("%d : %d -> %d\n",num,from,to);//실제 원판3이 from(1) -> to(3) 이동
//num:3 from:1 to:3
14: hanoi(m,from,to,num-1); // 원판2가 m(2) -> to(3)로 이동
//m:2 from:1 to:3 num-1:2
15: }
16: }
17: 😀 지금까지 재귀메서드를 다 돌면서
12: 에서 return 받고
13: 코드가 실행되어 실제 원판3이 from(1) -> to(3)으로 이동하게 된다.
그 다음에,
14: 재귀메서드가 실행 될 것이고, 원판2를 m(2) -> to(3)으로 이동시키기 위해서 원판1이 재귀호출되어 (2)->(1)로 이동시킨 다음에 다시 원판 2를 (2) -> (3) 로 이동시키고, 원판1도 (1) -> (3)으로 이동되면서 하노이탑은 종료가 될 것이다. 아래 그림을 살펴보고 마무리 하도록 하겠다.
✔ 재귀호출 되어 num=1 일 때)
✔ num=2 일 때)
✔ num=1 일 때)
😀 자세한 코드의 흐름은 지금까지 재귀호출하면서 코드 실행했던 것과 똑같이 반복됨으로 스스로 코드의 흐름을 그려보기도하고, 써보면서 이해 해보도록 하자.
여기에서 하노이 탑 설명은 마무리 짓도록 하겠다.
마지막으로, 필자와 같이 오랜시간 하노이 탑을 이해 못하고, 내 머리가 나쁜건가... 생각이 드는 독자분들이 있을 거 같아서 몇마디 하자면,,
필자도 하노이 탑을 이해하는데까지 오랜시간이 걸렸다...
물론, 매일 같이 하노이 탑을 이해하기 위해서 매달린 것이 아니었으니 저정도의 시간이 걸린 거 같다. (처음에는 3일정도 계속 이해라려고 애를 썼는데,, 그 때 느낀 것이 고등학교 때 수학문제 풀다보면 어려운 문제도 시간 지나서 다시 풀면 풀리듯이 하노이 탑도 시간 지나서 틈틈히 이해하려고 노력했다..)
필자가 하노이 탑을 이해하는데 중요하다고 생각되었던 부분이 재귀함수에 대한 이해가 확실하게 정립했어야 했고, 그 다음에 계속 그려보고, 써보면서 하노이 탑을 이해하려고 노력했다.
그리고 틈틈이 이해하려고 노력한다면 어느 날 딱! 이해하는 때가 올 것이다..
긴 글 끝까지 읽어주셔서 감사합니다 : )
포스팅은 스스로 습득한 지식과
강의, 블로그, 서적 등을 참고해서 이해한 것을 바탕으로 정보를 공유합니다.
포스팅에 문제가 있거나, 수정이 필요한 부분 , 질문이 있으시면 댓글 남겨주세요.
도움이 되셨다면 공감(♥)버튼, 댓글은 작성자에게 큰 힘이 됩니다.
댓글