2210)숫자판 점프

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

문제에서 제시된 규칙대로 숫자판에 접근해 만들어 질 수 있는 수는 아주 많다.

또한 중복되는 수들도 많기 때문에 중복되지 않게 규칙대로 만들어지는 수들을 저장해야 한다.

우선 규칙대로 수를 만드는 방법에 대해 생각해보자.

이를 위해 4방향으로 탐색하는 재귀함수를 응용했다.

count를 이용해 6번 방향탐색을 한다.

숫자판의 각 숫자에 접근해 그 숫자들을 기록해야 한다.

value 값을 10을 곱한 뒤(초기값 0)

기존 원소를 기준으로 동서남북 방향의 원소에 접근해 얻은 값을value에 합산한다.

그리고 이 value를 다음 호출할 함수로 넘긴다.

예를 들어 방향탐색에 의해 순서대로 1->2->3 순으로 접근한다고 하자.

value = 0에서 value*=10후에 value += 1을 한 결과 value는 1이다.

value = 1에서 value*=10후에 value += 2을 한 결과 value는 12이다.

value = 12에서 value*=10후에 value += 3을 한 결과 value는 123이다.

재귀함수가 숫자판의 각 숫자에 접근한 순서대로 수를 만들어 낼 수 있다.

재귀함수를 6번 호출했을 때, 링크 리스트에 value에 해당하는 값이 있는 지 검사한다.

value에 해당하는 값이 없다면 링크 리스트에 추가한다.

숫자판의 모든 숫자에 접근한 후 링크 리스트를 따라가며 노드의 수를 센 결과를 출력한다.

#include<stdio.h>
 
typedef enum _BOOL {
    TRUE = 1, FALSE = 0
}BOOL;
 
typedef struct _LINKLIST {
    int data;
    struct _LINKLIST *next;
}LINKLIST;
 
LINKLIST *list = NULL;
 
void createNode(int data) {
    LINKLIST *newNode;
    LINKLIST *last;
 
    newNode = (LINKLIST *)malloc(sizeof(LINKLIST));
    
    newNode->data = data;
    newNode->next = NULL;
 
    if (list != NULL) {
        last = list;
        while (last->next != NULL) {
            last = last->next;
        }
        last->next = newNode;
    }
    else {
        list = newNode;
    }
}
 
BOOL isExist(int data) {
    LINKLIST *p;
 
    p = list;
    while (p !=NULL) {
        if (p->data == data) return TRUE;
        p = p->next;
    }
    return FALSE;
}
 
int countNode() {
    LINKLIST *p;
    int count = 0;
 
    p = list;
    while (p != NULL) {
        count++;
        p = p->next;
    }
    return count;
}
 
void calJumpNum(int board[5][5], int i, int j, int value,int count) {
    if (count == 6) {
        if (!isExist(value)) {
            createNode(value);
        }
        return;
        
    }
    value = value * 10;
    value += board[i][j];
 
    count++;
    if(j+1<5) calJumpNum(board, i, j+1, value, count);
    if(i+1<5) calJumpNum(board, i+1, j, value, count);
    if(j-1>=0)calJumpNum(board, i, j-1, value, count);
    if(i-1>=0)calJumpNum(board, i-1, j, value, count);
}
 
int main() {
    int board[5][5];
 
    for (int i = 0; i < 5;i++) {
        for (int j = 0; j < 5;j++) {
            scanf("%d",&board[i][j]);
        }
    }
 
    for (int i = 0; i < 5;i++) {
        for (int j = 0; j < 5;j++) {
            calJumpNum(board, i,j,0,0);
        }
    }
    printf("%d\n", countNode());
    
    return 0;
}