[C] 백준 15651번: N과 M (3) - Linked List

https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

typedef struct Node {
	struct Node* prev;
	struct Node* next;
	int value;
}Node;

Node* getNode(int value) {
	Node* newNode = malloc(sizeof(Node));
	newNode->value = value;
	
	return newNode;
}

void r(int N, int count, Node* header, Node* trailer) {
	if (count == 0) {
		Node* cur = header->next;
		while (cur != trailer) {
			printf("%d ", cur->value);
			cur = cur->next;
		}
		printf("\n");

		return;
	}

	for (int i = 1; i < N + 1; i++) {
		Node* newNode = getNode(i);
		trailer->prev->next = newNode;
		newNode->prev = trailer->prev;
		newNode->next = trailer;
		trailer->prev = newNode;

		r(N, count - 1, header, trailer);

		Node* toFree = trailer->prev;
		trailer->prev->prev->next = trailer;
		trailer->prev = trailer->prev->prev;
		free(toFree);
	}
}

void freeNodes(Node* header) {
	Node* cur = header;

	while (cur) {
		Node* next = cur->next;
		free(cur);
		
		cur = next;
	}
}

int main() {
	int N, M;
	scanf("%d %d", &N, &M);

	// Initialize LL
	Node* header = malloc(sizeof(Node));
	Node* trailer = malloc(sizeof(Node));
	header->value = NULL;
	trailer->value = NULL;
	header->next = trailer;
	header->prev = NULL;
	trailer->next = NULL;
	trailer->prev = header;

	// Solution
	r(N, M, header, trailer);

	// Free
	freeNodes(header);

	return 0;
}

백트레킹을 이용하였으며, LinkedList로 일련된 숫자들을 계속해서 추가해주며, base case에서 이를 기반으로 출력해준다.