처음 풀어본 알고리즘 문제인데 이틀이 꼬박 걸렸습니다. 그런데 모범답안보니 너무 간단하네요. ㅠ 하노이탑 이동 원리를 아는 것 자체는 사실 무의미하지만 이 문제를 푸는 사고 과정 자체가 확립 되는 것이 중요할 것 같습니다. 머리 좋은 사람 참 많네요. 전 모범답안 보고도 한참 헤맸는데..
재귀함수가 모두 그렇듯, 키 포인트는 함수 자체가 계속 부분집합으로 발생했다 없어지는 방식이라는 것입니다. 일반적인 사고 방식과 같이(저처럼..) 전체를 보면서 풀어나가면 답이 없습니다. 제가 이틀 걸려 짠 코드는 가장 아랫쪽에 남겨둡니다. 흑역사네요. 간단히 3개짜리 원판 옮기기 구조만 보면 나머지는 로직만 주고 컴퓨터에게 맡길 수 있습니다. 실제로 원판이 7개쯤 되면 손으로 그리기도 힘듭니다.
세 개짜리 원판에서 가장 아래쪽에 있는 3이 목적지인 Z로 가기 위해서는 그 위의 숫자들을 전부 Y로 보내야 합니다.
3은 그 위가 Y로 모두 이동하고 나면 Z로 가면 되니 없는 셈 치고 두 개짜리만 신경씁니다. 2개보다 더 많을 때는 손으로 그리기도 꽤 힘든데 2개만 있을 때는 아주 간단히 3단계면 이동이 가능합니다.
즉 원판이 3개(n개) 있을 때, 그 위의 2개(n-1)을 최종 목적지 반대방향으로 이동시켜 준 후 3이 이동하면 된다는 의미입니다. 이 과정을 함수로 표현해보면 아래와 같습니다.
move함수 (이동할 원판 갯수, 출발지, 목적지, 나머지)
결국 최종적으로 원판이 2개만 있는 함수까지 재귀적으로 계속 들어갑니다.
쭉쭉 타고 들어가다가 마지막에 도달하면, 1의 경로를 찍어주고 리턴시킵니다. 재귀함수 탈출 구문입니다. 1에서 출력하고 리턴시키는 이유는 2개의 덩어리가 한 쌍이기 때문입니다. 원판 갯수가 한 개만 들어올 때는 재귀함수 실행 이전에 탈출구문에서 경로를 찍어주고 탈출하기 때문에 2개 단위로 구성해도 문제가 없습니다. 해보시면 알겠지만 2개 단위일 때 세 번의 단계가 있기 때문에 한 개단위로는 경로를 올바르게 순서대로 찍을 수가 없습니다.
마지막 함수가 리턴되면 1이 Z에 가 있게 되고 이제 2가 Y로 가야하는 차례이기 때문에 이 경로를 출력해줍니다.
그리고 다시 마지막 순서를 수행합니다. 원판 갯수가 현재 2개짜리인 함수에 있으니까 원판 갯수를 하나 줄여주고(count - 1), 순서를 Z→Y로 바라보게 만들어 줍니다. 다시 count == 1인 함수가 실행됐고 탈출 구문에 걸려서 경로를 출력하고 리턴됩니다.
이제 count==2의 함수도 끝에 도달했으므로 리턴되고 count==3의 함수로 돌아갑니다.
이제 count==3 함수에서 다음 차례가 실행됩니다. X→Z경로를 출력 한 후, 다시 반대경로(Y)에 있는 숫자를 Z로 보내주는 함수를 실행합니다.
이제 Y→Z로 다시 함수가 실행되면 위의 과정을 반복하고, 모두 리턴되면 첫 함수인 count==3은 최종 리턴되어 재귀함수가 종료됩니다. 로직이 완성되었으므로 이제 count에 무슨 숫자를 넣어도 컴퓨터가 알아서 계산해서 출력해줍니다.
알고나면 위의 로직은 참 간단합니다. 하지만 그 "아는 것"까지가 어려운 것 같습니다. 저만 그런가요..? ㅎㅎ 하노이 알고리즘같은건 사실 몰라도 무방합니다만, 위의 과정을 추론해내는 사고력이 문제가 되겠네요. 항상 아래 과정으로 생각하는 사고 구조가 필요할 것 같습니다.
- 무언가 같은 내용이 반복된다.
- 일정한 순서대로 반복되는 것이 아닌, 앞의 내용에 영향을 받아서 기준이 달라지며 반복된다.
- 재귀함수를 의심한다.
- 커다란 로직을 최대한 작게 쪼개본다.
- 최소한으로 쪼개진 단위에 일정한 규칙이 있고, 이 규칙이 큰 단위에도 그대로 적용된다.
- 최소한의 규칙에 맞게 재귀함수를 짠다.
아래 코드는 백준 알고리즘 제출용으로 약간 수정된 코드입니다. 사이트에 올릴 때는 제약이 많네요. 일단 최종 횟수를 제일 위에 출력해야하는데 함수가 끝나봐야 알 수 있어서 gotoxy()함수로 위에다 출력하려니 컴파일 에러가 뜹니다. 또 scanf_s()함수를 써도 컴파일 에러가 뜨네요. 제출하는 것만 엄청 헤맸습니다.
※ 백준 알고리즘 채점 제출 시 유의사항
1. scanf_s() 함수는 컴파일 에러가 뜬다. (다른 _s함수도 비슷한 가능성이 높음)
2. windows.h 전처리기 삽입 시에도 컴파일 에러가 뜬다.
3. 입력 범위가 지정된 경우, 이에 대한 처리를 해주지 않으면 런타임 에러가 뜬다.
그래서 그냥 아래처럼 함수를 두 번 돌려서 한 번은 카운트만 하고 한번은 출력만 하는 것으로 하니 정답 처리 되는군요. 뭔가 다른 방법이 있을 것도 같지만 그냥 여기까지만 하겠습니다. 중요한 건 제출이 아니니까요..!
#include <stdio.h>
int move_count;
/* 탑 옮기기 카운트용 */
/* parameter : 원판 갯수, 출발지, 도착지, 그 외 */
/* return : void */
void move(int count, int from, int to, int x)
{
/* 마지막 도달 시 재귀함수 탈출(마지막에서만 실행) */
if (count <= 1) {
move_count++;
return; // 가장 윗부분(1)에 도달하면 경로 출력 후 리턴
}
/* 마지막 도달 전 */
move(count - 1, from, x, to); // 바로 윗 숫자 덩어리는 도착지가 바뀜
move_count++;
move(count - 1, x, to, from);
}
/* 탑 옮기기 */
/* parameter : 원판 갯수, 출발지, 도착지, 그 외 */
/* return : void */
void move2(int count, int from, int to, int x)
{
/* 마지막 도달 시 재귀함수 탈출(마지막에서만 실행) */
if (count <= 1) {
printf("%d %d\n", from, to);
return; // 가장 윗부분(1)에 도달하면 경로 출력 후 리턴
}
/* 마지막 도달 전 */
move2(count - 1, from, x, to); // 바로 윗 숫자 덩어리는 도착지가 바뀜
printf("%d %d\n", from, to); // 현재 경로를 출력
move2(count - 1, x, to, from);
}
int main()
{
int count;
scanf("%d", &count);
if (count < 1 || count > 20)
return 0;
move_count = 0;
move(count, 1, 3, 2); // 최종 횟수 카운트
printf("%d\n", move_count); // 최종 횟수 출력
move2(count, 1, 3, 2); // 최초 1→3번으로 출발
return 0;
}
아래는 처음 짠 코드입니다. 실제로 배열에 값을 넣어서 옮기면서 수행하느라 코드가 지저분한데다 로직도 너무 복잡하네요. 그래도 결과는 일단 동일하게 나오긴 합니다.ㅋ 혹시 어렵다 느끼시는 분들은 아래 코드를 보면서 위안을 느끼시길..
#include <stdio.h>
void move_tower(int a, int b, int c);
int counter(int arr[][20], int a, int c, int x, int z);
void index_p(int a, int b, int c, int** x, int** y, int** z);
int comp(int arr[][20], int source, int dest);
void move(int arr[][20], int source, int dest);
int move_count;
int count;
int n; // 1번 장대 최초 원판 갯수 ( 1<= n <= 20)
int i; // 2번 장대 원판 갯수
int j; // 3번 장대 원판 갯수
/* 장대 3개 배열 생성 */
int arr[3][20];
int main()
{
count = 1;
while (count <= 20) {
/* 각 배열 인덱스 */
i = 0;
j = 0;
n = count;
move_count = 0;
/* 배열 초기화 */
for (int i = 0; i < 3; i++)
for (int j = 0; j < 20; j++)
arr[i][j] = 21;
/* 초기 원판 값 입력 */
for (int i = count, j = 0; i > 0; i--, j++)
arr[0][j] = i;
/* 2의 count제곱 구하기 */
int square = 1;
for (int i = 0; i < count; i++)
square *= 2;
/* 탑 옮기기 수행 */
move_tower(0, 2, 1);
printf("%d개 원판일 때 : %d번 (2^count-1 = %d)\n",
count, move_count, square - 1);
count++;
}
return 0;
}
/* 원판 옮기기 */
/* parameter : 배열 arr, */
/* return : void */
void move_tower(int a, int b, int c)
{
/* 해당 배열 짝을 맞추기 위한 포인터 생성 */
int* x = NULL, * y = NULL, * z = NULL;
index_p(a, b, c, &x, &y, &z);
if (x == NULL || y == NULL || z == NULL) // Waring 방지
return;
/* 갯수 기준은 이전 c에서 이동해야할 숫자보다 작은 숫자 */
int a_counter = counter(arr, a, c, *x, *z);
int temp; // 재귀 함수 실행 후 다른곳에서 옮겨오거나 옮겨간 원판 갯수 조정
while (a_counter > 0) {
if (a_counter % 2 == 1) { // 홀수라면 이동해야할 방향으로 이동
// 가능하면 이동
if ((*y > 0 && arr[a][*x - 1] < arr[b][*y - 1]) || *y == 0) {
move_count++;
move(arr, a, b);
a_counter--; // 카운터(갯수) 감소
}
else { // 불가능하면 기준을 바꿔서 다시 수행
temp = *x;
move_tower(b, c, a);
a_counter += (*x - temp);
}
}
else if (a_counter % 2 == 0) { // 짝수라면 이동해야할 방향 반대로 이동
// 가능하면 이동
if ((*z > 0 && arr[a][*x - 1] < arr[c][*z - 1]) || *z == 0) {
move_count++;
move(arr, a, c);
a_counter--;
}
else { // 불가능하면 기준을 바꿔서 다시 수행
temp = *x;
move_tower(c, b, a);
a_counter += (*x - temp);
}
}
}
if (j >= count) // 2번 장대에 모든 원판이 가면 재귀함수 종료
return;
if (i == 0) // 1번 장대가 모두 비었다면 0번 장대로 가서 재수행
move_tower(0, 2, 1);
else if (n == 0) // 0번 장대가 모두 비었다면 1번 장대로 가서 재수행
move_tower(1, 2, 0);
}
/* c보다 작은 a의 갯수 */
/* parameter : 배열인덱스 a,c와 해당 인덱스 넘버 */
/* return : c보다 작은 a의 갯수 */
int counter(int arr[][20], int a, int c, int x, int z)
{
int i, count;
for (i = 0; i < x; i++) {
if (z == 0)
break;
if (arr[a][i] < arr[c][z - 1])
break;
}
return (count = x - i);
}
/* 배열 인덱스에 따른 인덱스 값 포인터 변수 생성 */
/* parameter : 인덱스 a,b,c, 인덱스 더블 포인터 x, y, z */
/* return : void */
void index_p(int a, int b, int c, int** x, int**y, int** z)
{
if (a == 0) *x = &n;
else if (a == 1) *x = &i;
else if (a == 2) *x = &j;
if (b == 0) *y = &n;
else if (b == 1) *y = &i;
else if (b == 2) *y = &j;
if (c == 0) *z = &n;
else if (c == 1) *z = &i;
else if (c == 2) *z = &j;
}
/* 이동 가능 비교 */
/* parameter : 비교할 장대 source, dest */
/* return : 가능 == 0, 불가능 == 1 */
int comp(int arr[][20], int source, int dest)
{
/* 하나도 없을 경우을 대비해서 미리 만들어줌 */
int x, y, z;
if (n > 0)
x = n - 1;
else x = n;
if (i > 0)
y = i - 1;
else y = i;
if (j > 0)
z = j - 1;
else z = j;
/* 비교 */
if (source == 0) {
if (dest == 1) {
if (arr[0][x] < arr[1][y])
return 0;
else return 1;
}
else {
if (arr[0][x] < arr[2][y])
return 0;
else return 1;
}
}
else if (source == 1) {
if (dest == 0) {
if (arr[1][y] < arr[0][x])
return 0;
else return 1;
}
else {
if (arr[1][y] < arr[2][z])
return 0;
else return 1;
}
}
else if (source == 2) {
if (dest == 0) {
if (arr[2][z] < arr[0][x])
return 0;
else return 1;
}
else {
if (arr[2][z] < arr[1][y])
return 0;
else return 1;
}
}
return 1;
}
/* source에서 dest로 하나 옮겨줌 */
/* parameter : 옮길 장대 source, dest */
/* return : void */
void move(int arr[][20], int source, int dest)
{
if (source == 0 && n > 0) {
if (dest == 1) {
arr[1][i++] = arr[0][--n];
arr[0][n] = 21;
}
else if (dest == 2) {
arr[2][j++] = arr[0][--n];
arr[0][n] = 21;
}
}
else if (source == 1 && i > 0) {
if (dest == 0) {
arr[0][n++] = arr[1][--i];
arr[1][i] = 21;
}
else if (dest == 2) {
arr[2][j++] = arr[1][--i];
arr[1][i] = 21;
}
}
else if (source == 2 && j > 0) {
if (dest == 0) {
arr[0][n++] = arr[2][--j];
arr[2][j] = 21;
}
else if (dest == 1) {
arr[1][i++] = arr[2][--j];
arr[2][j] = 21;
}
}
}'▸알고리즘 문제 풀이' 카테고리의 다른 글
| 프로그래머스_해시_위장 (JAVA) (0) | 2020.04.15 |
|---|---|
| 프로그래머스_해시_전화번호 목록 (JAVA) (1) | 2020.04.14 |
| 프로그래머스_해시_완주하지 못한 선수 (JAVA) (4) | 2020.04.14 |
| 백준알고리즘_2751_정렬 (힙정렬) (C언어) (0) | 2019.12.09 |
| 백준알고리즘_10870_재귀함수_피보나치수열 (C언어) (0) | 2019.12.09 |
댓글