[알고리즘] 2개의 사탕

https://www.codetree.ai/training-field/frequent-problems/problems/two-candies/description?page=4&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

나의 풀이

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

#define MAX_SIZE 10

int _N;
int _M;

typedef struct node_s node_t;
struct node_s {
    int R_loc[2];
    int B_loc[2];
    int try_number;
    node_t* prev;
    node_t* next;
};

typedef struct queue_s queue_t;
struct queue_s {
    node_t *head;
    node_t *tail;
    int len;
};

void init(queue_t *queue) {
    queue->head = (node_t *) malloc(sizeof(node_t));
    queue->tail = (node_t *) malloc(sizeof(node_t));
    queue->head->next = queue->tail;
    queue->tail->prev = queue->head;
    queue->len = 0;
}

node_t* pop(queue_t *queue) {
    if (queue->head->next == queue->tail) {
        fprintf(stderr, "Error: delete from empty queue\n");
        exit(EXIT_FAILURE);
    } 

    node_t* pop_node = queue->tail->prev;
    node_t* temp = pop_node->prev;
    temp->next = queue->tail;
    queue->tail->prev = temp;
    queue->len--;

    return pop_node;
}

node_t* make_node(int R_loc[2], int B_loc[2], int try_number) {
    node_t *new_node = (node_t *) malloc(sizeof(node_t));
    memcpy(new_node->R_loc, R_loc, sizeof(new_node->R_loc));
    memcpy(new_node->B_loc, B_loc, sizeof(new_node->B_loc));
    new_node->try_number = try_number;

    return new_node;
}

void insert(queue_t *queue, node_t* new_node) {
    node_t* temp = queue->head->next;
    new_node->next = temp;
    temp->prev = new_node;
    queue->head->next = new_node;
    new_node->prev = queue->head;
    queue->len++;
}

bool is_empty(queue_t* queue) {
    if (queue->len == 0) {
        return true;
    }
    else {
        return false;
    }
}

void print(queue_t *queue) {
    node_t *curr = queue->head->next;
    while (curr->next != NULL) {
        printf("%d<-", curr->try_number);
        curr = curr->next;
    }
}

node_t *move(char** map, int R_loc[2], int B_loc[2], int dir, int try_number) {
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, -1, 0, 1};
    
    int candies_loc[2][2];
    memcpy(candies_loc[0], R_loc, sizeof(candies_loc[0]));
    memcpy(candies_loc[1], B_loc, sizeof(candies_loc[1])); 

    int moved_candies_loc[2][2];
    for (int i = 0; i < 2; i++) {
        int temp[2] = {candies_loc[i][0], candies_loc[i][1]};
        while (true) {
            int nx = temp[0] + dx[dir];
            int ny = temp[1] + dy[dir];

            if (map[nx][ny] == '#') {
                break;
            }

            if (map[temp[0]][temp[1]] == 'O') {
                break;
            }

            temp[0] = nx;
            temp[1] = ny;
        }
        for (int j = 0; j < 2; j++) {
            moved_candies_loc[i][j] = temp[j];
        }
    }

    if (memcmp(moved_candies_loc[0], moved_candies_loc[1], sizeof(moved_candies_loc[0])) == 0 && map[moved_candies_loc[0][0]][moved_candies_loc[0][1]] != 'O') {
        if (dir == 0) {
            if (candies_loc[0][0] > candies_loc[1][0]) {
                moved_candies_loc[0][0] -= dx[dir];
            }
            else {
                moved_candies_loc[1][0] -= dx[dir];
            }
        }
        if (dir == 2) {
            if (candies_loc[0][0] < candies_loc[1][0]) {
                moved_candies_loc[0][0] -= dx[dir];
            }
            else {
                moved_candies_loc[1][0] -= dx[dir];
            }
        }
        if (dir == 1) {
            if (candies_loc[0][1] > candies_loc[1][1]) {
                moved_candies_loc[0][1] -= dy[dir];
            }
            else {
                moved_candies_loc[1][1] -= dy[dir];
            }
        }
        if (dir == 3) {
            if (candies_loc[0][1] < candies_loc[1][1]) {
                moved_candies_loc[0][1] -= dy[dir];
            }
            else {
                moved_candies_loc[1][1] -= dy[dir];
            }
        }
    }
    
    node_t *node = make_node(moved_candies_loc[0], moved_candies_loc[1], try_number);
    return node;
}

int find_solution_bfs(char** map, queue_t* queue) {
    bool visited[MAX_SIZE][MAX_SIZE][MAX_SIZE][MAX_SIZE] = {false};

    int B_loc[2];
    int R_loc[2];
    int O_loc[2];
    for (int i = 0; i < _N; i++) {
        for (int j = 0; j < _M; j++) {
            if (map[i][j] == 'R') {
                R_loc[0] = i;
                R_loc[1] = j;
            }
            
            if (map[i][j] == 'B') {
                B_loc[0] = i;
                B_loc[1] = j;
            }
            
            if (map[i][j] == 'O') {
                O_loc[0] = i;
                O_loc[1] = j;
            }
        }
    }

    node_t* node = make_node(R_loc, B_loc, 0);
    insert(queue, node);
    visited[R_loc[0]][R_loc[1]][B_loc[0]][B_loc[1]] = true;

    while (!is_empty(queue)) {
        node_t* node = pop(queue);
        memcpy(R_loc, node->R_loc, sizeof(R_loc));
        memcpy(B_loc, node->B_loc, sizeof(B_loc));
        int try_number = node->try_number;
        // printf("%d %d %d %d\n", R_loc[0], R_loc[1], B_loc[0], B_loc[1]);
        free(node);
        if (try_number >= 11) {
            return -1;
        }

        if (memcmp(B_loc, O_loc, sizeof(B_loc)) == 0) {
            continue;
        }
        if (memcmp(R_loc, O_loc, sizeof(R_loc)) == 0) {
            return try_number ;
        }
        for (int i = 0; i < 4; i++) {
            node_t* next_node = move(map, R_loc, B_loc, i, try_number + 1);
            int next_R_loc[2] = {next_node->R_loc[0], next_node->R_loc[1]};
            int next_B_loc[2] = {next_node->B_loc[0], next_node->B_loc[1]};

            if (!visited[next_R_loc[0]][next_R_loc[1]][next_B_loc[0]][next_B_loc[1]]) {
                visited[next_R_loc[0]][next_R_loc[1]][next_B_loc[0]][next_B_loc[1]] = true;
                insert(queue, next_node);
            } 
        }
    }
    return -1;
}

int main() {
    queue_t *queue;

    scanf("%d %d", &_N, &_M);
    char **map = (char **) malloc(_N * sizeof(char *));
    for (int i = 0; i < _N; i++) {
        map[i] = (char *)malloc((_M + 1) * sizeof(char));
    }

    for (int i = 0; i < _N; i++) {
        scanf("%s", map[i]);
    }
    
    queue = (queue_t *) malloc(sizeof(queue_t));
    init(queue);
    
    int answer = find_solution_bfs(map, queue);
    printf("%d", answer);

    while (!is_empty(queue)) {
        node_t* node = pop(queue);
        free(node);
    }
    free(queue->head);
    free(queue->tail);
    free(queue);
}

- 메모리가 초과나는 문제가 있었는데 아마 같은 경우가 계속 들어가는 경우도 있어서 그럴 것이다. 이 경우를 visited로 체크해주니 해결이 되었다. 그도 그럴 것이 queue 안에 2 ^ 20 만큼이 들어갈 수도 있는데 이는 약 100만이 될 것이다. 100만 * 28 Byte = 2GB를 먹기 때문이다.

 

105             if (map[temp[0]][temp[1]] == 'O') {
106                 break;
107             }

위 부분도 실수했는데 저 인덱스에 nx, ny를 넣었었다. 그렇게 되면 그 다음이 'O'이기 때문에 'O' 전에 멈추게 되는 것이다. 그런데 이 코드의 종료 조건은 'O'에 있을때이기 때문에 종료조건을 만족할 수 없었던 것이다.

 

117     if (memcmp(moved_candies_loc[0], moved_candies_loc[1], sizeof(moved_candies_loc    [0])) == 0 && map[moved_candies_loc[0][0]][moved_candies_loc[0][1]] != 'O') {
118         if (dir == 0) {
119             if (candies_loc[0][0] > candies_loc[1][0]) {
120                 moved_candies_loc[0][0] -= dx[dir];
121             }
122             else {
123                 moved_candies_loc[1][0] -= dx[dir];
124             }
125         }
126         if (dir == 2) {
127             if (candies_loc[0][0] < candies_loc[1][0]) {
128                 moved_candies_loc[0][0] -= dx[dir];
129             }
130             else {
131                 moved_candies_loc[1][0] -= dx[dir];
132             }
133         }
134         if (dir == 1) {
135             if (candies_loc[0][1] > candies_loc[1][1]) {
136                 moved_candies_loc[0][1] -= dy[dir];
137             }
138             else {
139                 moved_candies_loc[1][1] -= dy[dir];
140             }
141         }
142         if (dir == 3) {
143             if (candies_loc[0][1] < candies_loc[1][1]) {
144                 moved_candies_loc[0][1] -= dy[dir];
145             }
146             else {
147                 moved_candies_loc[1][1] -= dy[dir];
148             }
149         }
150     }

 

- 위 코드의 경우에는 일단 굴리고 난 후 겹친 구슬에 대해서 구슬은 겹칠 수 없기 때문에 보정을 해주는 것이다.

- 나름 컴팩트하게 작성했다고는 생각하는데(굴릴 때마다 생각하는 것보다) 다른 분들의 코드도 참고해보면 좋을 거 같다.