[알고리즘][C] 마법의 숲 탐색

#include <stdio.h>
#include <string.h>

#define MAX_MAP_SIZE 70

int _R;
int _C;
int _time = 1;
int _dr[4] = {-1, 0, 1, 0};
int _dc[4] = {0, 1, 0, -1};

typedef struct Pos {
    int r;
    int c;
} Pos;

typedef struct Golem {
    Pos center;
    int exit_dir;
} Golem;

Pos try_down(int map[][MAX_MAP_SIZE], Golem golem) {
    // 밑으로 갈 수 있다면 움직이고 위치 반환 아니면 NULL 반환
    for (int i = 1; i < 4; i++) {
        Pos cur_pos;
        cur_pos.r = golem.center.r + _dr[i];
        cur_pos.c = golem.center.c + _dc[i];

        cur_pos.r++;
        if (cur_pos.r >= _R || (cur_pos.r >= 0 && map[cur_pos.r][cur_pos.c] != 0)) {
            return (Pos) {-3, -3};
        }
    }
    
    Pos ret_pos;
    ret_pos.r = golem.center.r + 1;
    ret_pos.c = golem.center.c;
    
    return ret_pos;
}

Pos try_left(int map[][MAX_MAP_SIZE], Golem golem) {
    // 왼쪽으로 갈 수 있다면 움직이고 위치 반환 아니면 NULL 반환
    for (int i = 0; i < 4; i++) {
        if (i == 1) {
            continue;
        }
        Pos cur_pos;
        cur_pos.r = golem.center.r + _dr[i];
        cur_pos.c = golem.center.c + _dc[i];

        cur_pos.c--;
        if (cur_pos.c < 0 || (cur_pos.r >= 0 && map[cur_pos.r][cur_pos.c] != 0)) {
            return (Pos) {-3, -3};
        }
    }

    golem.center.c--;
    if (try_down(map, golem).r == -3) {
        return (Pos) {-3, -3};
    }

    Pos ret_pos;
    ret_pos.r = golem.center.r + 1;
    ret_pos.c = golem.center.c;

    return ret_pos;
}

Pos try_right(int map[][MAX_MAP_SIZE], Golem golem) {
    // 밑으로 갈 수 있다면 움직이고 위치 반환 아니면 NULL 반환

    for (int i = 0; i < 3; i++) {
        Pos cur_pos;
        cur_pos.r = golem.center.r + _dr[i];
        cur_pos.c = golem.center.c + _dc[i];

        cur_pos.c++;
        if (cur_pos.c >= _C || (cur_pos.r >= 0 && map[cur_pos.r][cur_pos.c] != 0)) {
            return (Pos) {-3, -3};
        }
    }

    golem.center.c++;
    if (try_down(map, golem).r == -3) {
        return (Pos) {-3, -3};
    }

    Pos ret_pos;
    ret_pos.r = golem.center.r + 1;
    ret_pos.c = golem.center.c;

    return ret_pos;
}

void print(int map[][MAX_MAP_SIZE]) {
    for (int i = 0; i < _R; i++) {
        for (int j = 0; j < _C; j++) {
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }
}

Pos move_golem(int map[][MAX_MAP_SIZE], int start_c, int start_dir) {
    
    Golem golem;
    golem.center = (Pos) {-2, start_c};
    golem.exit_dir = start_dir;

    while (1) {
        Pos temp_center;
        if ((temp_center = try_down(map, golem)).r != -3) {
            golem.center = temp_center;
            continue;
        }
        if ((temp_center = try_left(map, golem)).r != -3) {
            golem.center = temp_center;
            golem.exit_dir = (3 + golem.exit_dir) % 4;
            continue;
        }
        if ((temp_center = try_right(map, golem)).r != -3) {
            golem.center = temp_center;
            golem.exit_dir = (1 + golem.exit_dir) % 4;
            continue;
        }

        break;
    }
    
    if (golem.center.r <= 0) {
        return golem.center;
    }

    map[golem.center.r][golem.center.c] = _time;
    for (int i = 0; i < 4; i++) {
        int nr = golem.center.r + _dr[i];
        int nc = golem.center.c + _dc[i];
        if (i == golem.exit_dir) {
            map[nr][nc] = -_time;
        } 
        else {
            map[nr][nc] = _time;
        }
    }
    
    // print(map);
    _time++;
    return golem.center;
}

Pos move_elf(int map[][MAX_MAP_SIZE], Pos elf_pos) {
    int visited[MAX_MAP_SIZE][MAX_MAP_SIZE];
    memset(visited, 0, sizeof(visited));
    // BFS하며 가장 큰 행이라면 갱신
    int max_pos = elf_pos.r + 1;
    Pos queue[4900];
    int start = 0;
    int end = 0;
    queue[end++] = elf_pos;
    visited[elf_pos.r][elf_pos.c] = 1;
    while (start < end) {
        Pos cur_pos = queue[start++];
        for (int i = 0; i < 4; i++) {
            int next_r = cur_pos.r + _dr[i];
            int next_c = cur_pos.c + _dc[i];

            if (!(0 <= next_r && next_r < _R && 0 <= next_c && next_c < _C)) {
                continue;
            }

            if (visited[next_r][next_c] == 1) {
                continue;
            }

            if (map[next_r][next_c] == 0) {
                continue;
            }

            if (map[cur_pos.r][cur_pos.c] == map[next_r][next_c] || map[next_r][next_c] == -map[cur_pos.r][cur_pos.c] || map[cur_pos.r][cur_pos.c] < 0) {
                visited[next_r][next_c] = 1;
                Pos next_pos = {next_r, next_c};
                queue[end++] = next_pos;
                if (max_pos < next_pos.r + 1) {
                    max_pos = next_pos.r + 1;
                }
            }
        }
    }
    
    Pos ret_pos;
    ret_pos.r = max_pos;
    return ret_pos;
}

int check_valid(Pos elf_pos) {
    if (elf_pos.r <= 0) {
        return 0;
    }

    return 1;
}

void reset_map(int map[][MAX_MAP_SIZE]) {
    for (int i = 0; i < _R; i++) {
        for (int j = 0; j < _C; j++) {
            map[i][j] = 0;
        }
    }
}

int find_elf_loc(int map[][MAX_MAP_SIZE], int start_loc, int start_dir) {
    Pos elf_pos = move_golem(map, start_loc, start_dir);
    // printf("elf_pos %d %d\n", elf_pos.r, elf_pos.c) ;
    if (!check_valid(elf_pos)) {
        reset_map(map);
        return 0;
    }

    Pos moved_elf_pos = move_elf(map, elf_pos);
    
    return moved_elf_pos.r;
}

int main() {
    int K;
    int result = 0;
    int map[MAX_MAP_SIZE][MAX_MAP_SIZE];
    
    scanf("%d %d %d", &_R, &_C, &K);
    reset_map(map);
    for (int i = 0; i < K; i++) {
        int start_c;
        int start_dir; // 0, 1, 2, 3 : 북, 동, 남, 서

        scanf("%d %d", &start_c, &start_dir);
        start_c--;
        int temp = find_elf_loc(map, start_c, start_dir);
        // printf("%d\n", temp);
        result += temp;
    }

    printf("%d\n", result);
}

나의 풀이

- _R과 _C을 이용하는 reset_map을 먼저 돌리고 _R, _C을 받았다. 그러니까 제대로된 결과가 나오지 않을 수밖에

- 또한 try_left, try_right 등에서 밑으로 가니까 golem.center.r + 1을 해야하는데 - 1을 했다.

- 밑의 golem.center.r 이걸로 아래로 갈때 런타임 안되게 막아줘야 하는데 몰랐고 틀린 이후 추가했다.

    if (golem.center.r <= 0) {
        return golem.center;
    }

- 인풋으로 들어오는 변수는 웬만해서는 글로벌 변수로 쓰는것이 합리적이다.