C - 12094 2048(hard)

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

 

2048(easy)에서 움직일 횟수가 10으로 증가한 문제다.

가능한 움직임횟수(depth)이 커져서 easy와 같이 백트래킹없이 전수조사를 하면 시간초과에 직면한다.

 

가지치기(분기한정)은 2가지를 했다.

a.한번 움직였는데 이전과 같다.

a를 만족하는 경우는 최선의 최댓값을 뽑기위한 이동횟수를 한번 낭비했으므로 더이상 탐색하지 않아도 된다.

더 이상 움직일 수 없는경우와 움직이지 않는 방향으로 움직이는 경우를 가지치기한다.

int IsNotChange(int lv) {
    if(lv == 0) return 0;
    for(i=0; i<size; i++)
        if(memcmp(&board[lv][i][0], &board[lv-1][i][0], mem_line_size)) return 0;
    return 1;
}

 

b.현재 탐색에서의 최대기댓값이 내가 이미 찾은 최댓값보다 낮거나 같을 경우

b는 2048의 규칙에 따라 조건으로 만들 수 있다. 예를 들어 현재 탐색에서 최댓값이 2^7이 찾아졌고

여기서 8번더 움직일 수 있다고 가정하면 최대기댓값은 2^(7+8)이 될 것이다. 이 최대기댓값이 내가 이미 찾은 최댓값보다 작거나 같으면 이 경우도 더 이상 탐색할 필요가 없다.

int IsNotUsefull(int lv) {
    if(lv == 0 ) return 0;
    //현재 2^6, 앞으로 3번더 움직일 수 있다면 2^9가 최대기대치 
    u_char possible_mxbit = max_tmp + (FIND_LV - lv);
    if(possible_mxbit <= final_max) return 1;
    return 0;
}

 

그리고 최적화를 몇가지 했다.

a.dfs안에서의 큰수의 곱셈이 고정된 결과값인 경우나 몇가지 변수를 외부로 꺼내어 같은결과를 다시 연산하거나 자주쓰이는 변수를 다시 할당하는 경우를 줄였다.

 

b.이전 코드에서 비효율적인 find_max()함수를 제거하고 move함수에 같이 탐색하도록 만들었다.

move함수에 이미 N에 대한 탐색을 실행하는데 여기서 같이 최댓값을 갱신하면되지 별도로 N을 탐색할 필요가 없음을 알았다.

 

c.기존에 배열에 2^x의 값들을 그대로 넣었는데 2^x로만 값들이 주어지고 결과도 2^x의 형태로 저장하는데

이를 x만 가져와서 저장하면 기존 int형보다 공간을 적게 소모할 수 있을것같았다. 그래서 지수만 저장해 탐색할 수 있도록했다.

주어지는값이 2^10이 최대이고 여기서 최대 기댓값은 2^(10+10)이므로 x의 범위는 20이하다.

따라서 unsigned char범위내에서 벗어나지 않으므로 이 타입으로 값을 저장하여 연산하도록 만들었다.

공간사용량을 개선했다.

 

https://github.com/shirohebiui/BAEKJOON/blob/3ad185ed981e627972520517ab6c5e4b6aaf18b7/%23DFS/P/12094(P2)2048(hard)/improve.c