교재 : C로 배우는 쉬운 자료구조
문제 : Chapter 04 - 응용예제 04 - 보물상자를 열어라!
구분 : 이중 원형 연결 리스트 (Doubly Circular Linked List) (=양방향 원형 연결 리스트)
<문제풀이>
이 문제를 풀기 위해서는 특정 보물상자를 기준으로 시계방향 또는 시계반대방향으로 자유롭게 이동할 수 있어야 한다.
그러므로 양방향으로 연결된 원형리스트를 구성한다.
보물상자의 개수는 입력을 받고 이 입력받은 값에 따라 다음 보물상자의 위치를 나타내는 숫자로 입력받을 개수가 달라진다.
입력 받은 N을 malloc을 통해 동적할당을 해주고, 그 안에다가 다음 보물상자의 위치를 나타낸 숫자를 n개 입력 받는다.
열어진 보물상자는 양방향 원형리스트에서 연결을 끊고, 메모리 할당도 해제한다.
처음 여는 보물 상자는 1번 보물 상자이고, 이 안에 들어 있는 값만큼 이동한다.
이때 음수는 시계반대방향, 양수는 시계방향으로 이동하게 된다.
1번 보물상자에 2가 들어있다면 시계방향으로 2칸 움직여서 다음에 열게 될 보물상자는 3번이다.
이후 1번 보물상자는 연결을 끊고 메모리 할당또한 해제한다.
3번 보물상자를 열고, 이 안에 들어있는 값으로 또 이동한 후, 3번 노드또한 연결과 할당을 해제한다.
이 루틴을 반복적으로 수행하여 열었던 보물상자의 번호를 순서대로 출력하면 된다.
먼저 이 알고리즘을 도식화 하면 다음 그림처럼 표현할 수 있다.
기준점은 빨간색 체크 표시이며, 다음으로 열게 될 보물상자가 된다.
이를 코드로 구현해보자.
#include<stdio.h>
#include<stdlib.h>
//보물상자 형식
typedef struct node {
int number; //보물상자의 번호
int offset; //다음 보물상자의 거리 (음수 : 역방향, 양수 : 정방향)
struct node* prev; //이전 노드의 주소
struct node* next; //다음 노드의 주소
} node;
node* head; //리스트의 head 선언 : 전역변수.
node* create_node(void) { //빈 노드 생성 함수
node* new_node;
new_node = (node*)malloc(sizeof(node));
new_node->number = 0;
new_node->offset = 0;
new_node->prev = NULL;
new_node->next = NULL;
return new_node;
}
//노드를 리스트 맨 마지막에 추가하는 함수.
void insert_node(node* new_node, int number, int offset) {
new_node = create_node();
new_node->prev = head->prev;
new_node->next = head;
new_node->prev->next = new_node;
new_node->next->prev = new_node;
new_node->number = number;
new_node->offset = offset;
}
/*//전체 리스트 출력 : 양방향 원형 리스트의 전체 값을 확인할 수 있다.
void print_list() {
node* node = head;
do {
printf("node의 prev : %p\n", node->prev);
printf("node의 addr : %p\n", node);
printf("node의 next : %p\n", node->next);
printf("node의 number : %d\n", node->number);
printf("node의 off : %d\n\n", node->offset);
node = node->next;
} while (node != head);
}
*/
//노드 연결 해제와 메모리 할당 해제
void unlink_node(node* node) {
if (node == head) head = node->next;
node->prev->next = node->next;
node->next->prev = node->prev;
free(node);
}
//보물상자를 여는 함수
node* open_treasure(node* node) {
int offset = node->offset; //현재 노드가 가지고 있는 다음 노드의 offset 값.
struct node* target; //node를 unlink하기 전 target에 주소 복사. target은 다음 기준 노드의 주소를 반환.
//현재 노드를 unlink하면서 free하기 때문에 이동할 진행방향의 반대로 노드 기준점을 설정한다.
if (offset < 0) target = node->next; //0보다 작으면 역방향으로 찾아야 하기 때문에 노드 기준점을 다음 노드로 설정.
else target = node->prev; //0보다 크면 정방향으로 찾아야 하기 때문에 노드 기준점을 이전 노드로 설정.
unlink_node(node); //노드를 연결리스트에서 연결을 끊고 메모리 할당도 해제한다.
//offset만큼 노드 이동 (음수면 역방향, 양수면 정방향)
while (offset != 0) { //offset이 0이 될 때 까지 반복.
if (offset < 0) { //0보다 작으면 역방향으로 찾는다.
target = target->prev;
offset++;
}
else if (offset > 0) { //0보다 크면 정방향으로 찾는다.
target = target->next;
offset--;
}
}
return target; //이동을 마친 노드 주소 반환
}
int main() {
int n;
scanf_s("%d", &n); // 1 <= n <= 10
int* offset = (int*)malloc(sizeof(int) * n); //n만큼 동적할당. offset는 각 노드 순서대로 다음 노드와의 거리.
for (int i = 0; i < n; i++) scanf_s("%d", &offset[i]);
//첫번째 노드(head)의 값 초기화 -> 보물상자 열기는 무조건 1번부터 시작한다.
head = create_node(); //빈 노드 생성.
head->number = 1; //상자는 1번부터 n번까지.
head->offset = offset[0]; //입력받은 offset배열에서 첫번째 값 대입.
head->prev = head; //양방향 원형리스트에 노드가 하나라면 prev와 next 모두 자신 노드를 가르킴.
head->next = head; //노드가 추가될 때 노드의 prev, next 값으로 포인터를 설정하기 때문이다
node* node = head; //노드의 시작 head(전역변수) 값은 보존시킨다.
//head(==node)를 기준으로 리스트의 tail로 데이터 삽입.
for (int i = 2; i <= n; i++) insert_node(node, i, offset[i - 1]);
free(offset);
do {
printf("%d ", node->number); //보물상자의 번호 출력 -> 첫 수행은 head인 1번 보물상자를 먼저 연다.
node = open_treasure(node); //다음 보물상자를 오픈하는 함수.
n--;
} while (n > 0); //노드의 개수는 입력받은 n이므로, n만큼 반복하면서 보물상자를 연다.
}<실행 결과>
* 첫번째 여는 상자를 입력받을 때.
#include<stdio.h>
#include<stdlib.h>
//보물상자 형식
typedef struct node {
int number; //보물상자의 번호
int offset; //다음 보물상자의 거리 (음수 : 역방향, 양수 : 정방향)
struct node* prev; //이전 노드의 주소
struct node* next; //다음 노드의 주소
} node;
node* head; //리스트의 head 선언 : 전역변수.
node* create_node(void) { //빈 노드 생성 함수
node* new_node;
new_node = (node*)malloc(sizeof(node));
new_node->number = 0;
new_node->offset = 0;
new_node->prev = NULL;
new_node->next = NULL;
return new_node;
}
//노드를 리스트 맨 마지막에 추가하는 함수.
void insert_node(node* new_node, int number, int offset) {
new_node = create_node();
new_node->prev = head->prev;
new_node->next = head;
new_node->prev->next = new_node;
new_node->next->prev = new_node;
new_node->number = number;
new_node->offset = offset;
}
/*//전체 리스트 출력 : 양방향 원형 리스트의 전체 값을 확인할 수 있다.
void print_list() {
node* node = head;
do {
printf("node의 prev : %p\n", node->prev);
printf("node의 addr : %p\n", node);
printf("node의 next : %p\n", node->next);
printf("node의 number : %d\n", node->number);
printf("node의 off : %d\n\n", node->offset);
node = node->next;
} while (node != head);
}
*/
//노드 연결 해제와 메모리 할당 해제
void unlink_node(node* node) {
if (node == head) head = node->next;
node->prev->next = node->next;
node->next->prev = node->prev;
free(node);
}
//보물상자를 여는 함수
node* open_treasure(node* node) {
int offset = node->offset; //현재 노드가 가지고 있는 다음 노드의 offset 값.
struct node* target; //node를 unlink하기 전 target에 주소 복사. target은 다음 기준 노드의 주소를 반환.
//현재 노드를 unlink하면서 free하기 때문에 이동할 진행방향의 반대로 노드 기준점을 설정한다.
if (offset < 0) target = node->next; //0보다 작으면 역방향으로 찾아야 하기 때문에 노드 기준점을 다음 노드로 설정.
else target = node->prev; //0보다 크면 정방향으로 찾아야 하기 때문에 노드 기준점을 이전 노드로 설정.
unlink_node(node); //노드를 연결리스트에서 연결을 끊고 메모리 할당도 해제한다.
//offset만큼 노드 이동 (음수면 역방향, 양수면 정방향)
while (offset != 0) { //offset이 0이 될 때 까지 반복.
if (offset < 0) { //0보다 작으면 역방향으로 찾는다.
target = target->prev;
offset++;
}
else if (offset > 0) { //0보다 크면 정방향으로 찾는다.
target = target->next;
offset--;
}
}
return target; //이동을 마친 노드 주소 반환
}
int main() {
int n, start_treasure;
printf(" 총 보물상자 개수 입력 : ");
scanf_s("%d", &n); // 1 <= n <= 10
int* offset = (int*)malloc(sizeof(int) * n); //n만큼 동적할당. offset는 각 노드 순서대로 다음 노드와의 거리.
printf(" 다음 상자의 offset 입력 (공백을 기준으로 n개 입력) : ");
for (int i = 0; i < n; i++) scanf_s("%d", &offset[i]);
printf(" 처음으로 오픈할 보물상자 숫자 입력 : ");
scanf_s("%d", &start_treasure);
//첫번째 노드(head)의 값 초기화 -> 입력받은 start_treasure 값부터 오픈한다..
head = create_node(); //빈 노드 생성.
head->number = start_treasure; // 입력받은 start_treasure 값 대입
head->offset = offset[start_treasure - 1]; //입력받은 offset배열에서 start_treasure-1값 대입 (배열의 인덱스가 0부터 시작하기 때문에 -1).
head->prev = head; //양방향 원형리스트에 노드가 하나라면 prev와 next 모두 자신 노드를 가르킴.
head->next = head; //노드가 추가될 때 노드의 prev, next 값으로 포인터를 설정하기 때문이다
node* node = head; //노드의 시작 head(전역변수) 값은 보존시킨다.
//head(==node)를 기준으로 리스트의 tail로 데이터 삽입. start_treasure부터 n삽입 후, 1부터 start_treasure 이전 수 까지 삽입.
for (int i = start_treasure + 1; i <= n; i++) insert_node(node, i, offset[i - 1]);
for (int i = 1; i < start_treasure; i++) insert_node(node, i, offset[i - 1]);
free(offset);
do {
printf("%d ", node->number); //현재 보물상자의 번호 출력
node = open_treasure(node); //다음 보물상자를 오픈하는 함수.
n--;
} while (n > 0); //노드의 개수는 입력받은 n이므로, n만큼 반복하면서 보물상자를 연다.
}
<실행 결과>
