백준 11729 | 재귀 함수, 하노이의 탑 이동 순서

재귀 함수

재귀란 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다.
즉, 어떤 함수를 호출하면 그 안에 어떤 함수를 또 호출하여 반복한다는 뜻이다.
쉽게 이해하려면 엘리베이터 거울을 생각하면 좋을 것 같다!
(내가 이걸로 이해했다.🥶)

처음에는 굉장히 생소한 이름이었지만 Node.js를 공부하며 콜백 지옥 이라는 내용을 접했는데, 여기서 콜백 이 재귀 함수의 개념을 포함하고 있다고 한다.(맞을거다..ㅎ)
사이버다임 면접을 준비하면서 재귀 함수에 대한 문제가 나온다는 이야기를 들었고, 이를 공부하기 위해서 하노이의 탑 문제를 풀어 봤는데 손으로 직접 그려 보기 전까지는 전혀 이해하지 못했다. 근데 한번 손으로 그려 보니까 완벽하지 않지만 대략적으로 재귀에 대한 틀이 잡힌 것 같다.
(정작 사이버다임 코딩테스트에서는 팩토리얼에 대한 문제가 출제됐다. 다음에 기회가 된다면 다뤄 봐야겠다.)(자세한 내용은 아래 블로그를 참고.)

 

반드시 알아야하는 알고리즘 top 8 - 1. 재귀 알고리즘

하노이의 탑 이동 순서 출력하기

하노이의 탑은 아기들이 가지고 노는 장난감같이 생겼는데, 나는 어렸을 때 이런 장난감은 안 갖고 놀아서 그런지 굉장히 익숙하지 않았다.

그래서 손으로 직접 그려 보기도 하고, 책도 참고하고, 유튜브 영상도 시청했다.
가장 쉽게 설명한 영상은 얄팍한 코딩 사전님이 올려 주신 영상이다.

 

그래서, 나는 공부한 것을 바탕으로 이렇게 써가며 문제를 풀어 봤다.

• 손으로 정리하는 것만 3시간은 걸린 것 같은 노트

처음에는 내가 나를 호출하고, 호출당한 내가 또 나를 호출하고, 호출당한 내가 호출한 내가 또 나를 호출하고... 이렇게 끝없이 반복되는 것이 너무 어려웠다.
여기서 함수를 호출하는 조건을 이해하고, 이 것을 위의 2 번째 그림으로 그려 보면 한층 더 이해하기 쉬워진다.

그래서 나는 이렇게 코드를 짰다.
(사실 하노이의 탑 문제는 거의 모든 사람들의 풀이가 비슷하다.)

• 누가 누가 잘 짰나

package 심성헌.알고리즘_3주차;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 하노이탑이동순서_11729 {

	static StringBuffer sb = new StringBuffer();
	static int count = 0;

	static public int move(int n, int x, int y) {
		if (n > 1) {
			move(n - 1, x, 6 - x - y);
		}

		sb.append(x + " " + y + "\n");
		count++;

		if (n > 1) {
			move(n - 1, 6 - x - y, y);
		}

		return count;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		int count = move(n, 1, 3);
		System.out.println(count);
		System.out.println(sb.toString());
	}

}

해당 코드에서 중요한 부분은 재귀적으로 반복하는 move() 함수도 있지만, 6 이라는 숫자는 왜 나왔는지를 파악하는 것이 중요하다.

 

구조 파악하기

위의 노트 내용을 참고하면, 결과적으로 3번 원반부터 1번 원반까지 3번 기둥으로 옮겨야 하는 것이 관건이다.

여기서 3번 원반을 3번 기둥으로 옮기기 위해서는 2번 원반을 먼저 다른 기둥으로 옮겨야 하고, 2번 기둥을 옮기기 위해서는 1번 원반을 먼저 다른 기둥으로 옮겨야 한다.

즉, 3번 원반을 3번 기둥을 옮기기 위해서 가장 기초가 되어야 하는 일이 1번 원반이 다른 기둥으로 이동해야 한다는 점이다.

(결과를 파악하고 결과를 도달하기 위해 시작점을 파악한다.)

그렇다면 현재 1번 기둥에 있는 3번 원반을 3번 기둥으로 이동하기 위해서는 1번 기둥에 있는 2번 원반을 2번 기둥으로 옮기고, 2번 원반을 옮기기 위해서는 1번 기둥에 있는 1번 원반을 3번 기둥으로 이동한다.

위의 로직을 파악하고 나면 모든 기둥에 원반이 하나씩 들어가 있는 그림이 그려질 것이다. 이제 진짜 3번 원반을 3번 기둥으로 옮기는 작업을 수행할 것이다.

1번 기둥 - 3번 원반
2번 기둥 - 2번 원반
3번 기둥 - 1번 원반

이러한 상태에서 3번 원반을 3번 기둥으로 옮기기 위해서는,
3번 기둥에 있는 1번 원반을 2번 원반으로 이동한다. 그 후, 1번 기둥에 있는 3번 원반을 3번 기둥으로 이동한다.
그렇다면 현재 구조는

1번 기둥 - 없음
2번 기둥 - 2번 원반 / 1번 원반
3번 기둥 - 3번 원반

위의 상태로 구성되어 있다. 3번 원반을 성공적으로 3번 기둥으로 옮겼다.
이제 2번 원반을 3번 기둥으로 옮겨야 한다.
2번 기둥에 있는 1번 원반을 1번 기둥으로 이동한 후, 2번 기둥에 있는 2번 원반을 3번 원반으로 이동한다. 이제 기둥의 구조는

1번 기둥 - 1번 원반
2번 기둥 - 없음
3번 기둥 - 3번 원반 / 2번 원반

로 구성되었다. 이제 1번 원반만 1번 기둥으로 옮기면 성공이다.
1번 기둥에 있는 1번 원반을 3번 기둥으로 이동한다.

1번 기둥 - 없음
2번 기둥 - 없음
3번 기둥 - 3번 원반 / 2번 원반 / 1번 원반

성공적으로 하노이의 이동 순서를 파악하고,원반을 옮겼다.
그렇다면 이제 왜 코드의 계산이 나온 이유를 파악해 보자!

파란색 형광펜은 이동해야 할 원반의 인덱스 번호다.

빨간색 형광펜은 이동해야 할 원반이 현재 위치하고 있는 기둥의 번호다.

노란색 형광펜은 원반이 이동해야 할 기둥의 번호다.

 

n - 1 의 이유

그렇다면 3번을 1번 기둥으로 이동하기 위해서 근본적으로 2번 원반을 이동해야 하고, 2번 원반을 이동하기 위해서는 1번 원반을 이동해야 한다.

즉, 결과를 도달하기 위해서는 결과 - 1 이다.

n = 3 / n - 1 = 2

n = 2 / n - 1 = 1

n = 1

이러한 로직을 가지기 때문에
재귀적으로 호출할 함수에 들어갈 원반의 값은 n - 1 이다.

 

6 - x - y 의 이유

원반의 번호가 어떻게 재귀적으로 변하는지 파악했다면, 현재 위치한 기둥의 번호와 이동해야 할 기둥의 번호가 어떻게 계산 되는지 파악해야 한다.
즉,

1. 1번 기둥에 위치한 3번 원반을 3번 기둥으로 이동한다는 것은
2. 1번 기둥에 위치한 2번 원반을 2번 기둥으로 이동해야 한다는 뜻이고,
3. 이는 1번 기둥에 위치한 1번 원반을 3번 기둥으로 이동해야 한다.

여기서 1번 기둥은 x, 현재 원반이 위치하고 있는 기둥의 번호다.
3번 기둥은 y , 원반이 이동해야 할 기둥의 번호다.
여기서 중요한 점은 1번을 수행하기 위해서는 2번이 선행되어야 하고, 2번이 선행하기 위해서는 3번을 선행되어야 한다는 것이다.
그렇다면 1번부터 3번 원반이 위치하고 있는 기둥은 1번 기둥으로 같으며, 1번을 수행하기 위해서는 2번 원한이 이동해야 할 기둥 번호를 알아야 한다는 것이다.

즉,

• 6(i) - 1(x) - 3(y) = 2(z)
• 1(x)* : 자신이 움직이기 전 아무런 변화가 없었다는 뜻.
• 3(y)* : 자신이 이동해야 할 기둥의 번호
• 2(z)* : 자신이 이동하기 위해서 선행되어야 할 움직임이 이동해야 할 기둥의 번호
• 6 - 1 - 3 = 2 과 1 + 3 + 2 = 6 은 같다.

x + y + z = i

i - y - z = x
i - x - z - y
i - x - y = z

우리는 위의 노트를 통해 1번 기둥(x)에 위치한 3번 원반(n)이 3번 기둥(y)으로 이동하기 위해서는 2번 원반(n - 1)이 2번 기둥(z = 6 - x - y)으로 이동해야 한다는 것을 알고 있다.

위 예시는 3번 원반을 이동하기 위해 2번 원반이 이동해야 할 기둥 번호를 유추하는 구조인데, 이 구조는 하노이 탑에서 어떤 경우에서도 동작한다.
그렇기에 현재의 원반(n)이 이동하기 위해서 다음 원반(n - 1)이 이동할 기둥의 번호를 유추하기 위해서는 6 이라는 숫자가 필요하다.

재귀적으로 해결하기

n 과 z 가 유추되는 방법을 파악했다면, 이제 이를 재귀적으로 그려 보자.
위에서 너무 많이 설명했다.

마무리

이번 문제를 풀면서 수리 사고가 정말 중요하다는 것을 느꼈다.
그리고 게으르게 머리로만 생각하지 말고, 직접 손으로 그려서 풀어 봐야 한다는 것을 깨달았다!