[백준 3190번] 뱀

http://www.acmicpc.net/problem/3190

3190번: 뱀

풀이) 

뱀의 몸에 닿으면 게임을 끝나는 조건을 설정할 때, 처음에 queue로 진행하려했으나, stl에서 자체적으로 제공하는 iterator가 없어서 linkedlist를 직접 구현하는 방식으로 진행했다. 구현문제였기때문에 문제에서 요구한 절차에 따라

방향에 따른 이동 -> 게임종료 조건 확인 -> 사과 먹은 유무에 따른 몸 길이 재 설정 -> 현 시간이 방향을 바꾸어야 하는 시점인지 확인으로 진행했고, 사과 위치, 뱀의 몸이 남아있는 위치, 시간에 따른 방향 설정정보들을 어떤식으로 저장하고 사용할지에 대해 명확하게 떠오르지 않아서 시간이 더 걸렸다.

#include <iostream>
#include <queue>
using namespace std;

int apple[101][2];
int N, K, L, now_x = 1, now_y = 1, time_, move_dir = 1, result = 0;
char dir;
char secondForDir[10001];

typedef struct node{
    int x, y;
    struct node* link;
} node;
struct node* head = NULL;

void add_list(int x, int y)
{
    struct node* add = (struct node*)malloc(sizeof(node));
    add->x = x;
    add->y = y;
    add->link = head;
    head = add;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> K;
    for (int i = 1; i <= K; i++)
        cin >> apple[i][0] >> apple[i][1];
    cin >> L;
    while (L--)
    {
        cin >> time_ >> dir;
        secondForDir[time_] = dir;
    }
    
    head = (struct node*)malloc(sizeof(node));
    head->x = 1;
    head->y = 1;
    head->link = NULL;
    
    while (1)
    {
        result++;
        bool apple_ = false, end = false;
        
        if (move_dir == 1)
            now_y += 1;
        else if (move_dir == 2)
            now_x += 1;
        else if (move_dir == 3)
            now_y -= 1;
        else if (move_dir == 4)
            now_x -= 1;
        
        struct node* p = head;
        while (p != NULL) {
            if (now_x == p->x && now_y == p->y)
                end = true;
            p = p->link;
        }
        if (now_x < 1 || now_x > N || now_y < 1 || now_y > N || end)
			break ;
        
        add_list(now_x, now_y);
    
        for (int t = 1; t <= K; t++){
            if (apple[t][0] == now_x && apple[t][1] == now_y){
                apple[t][0] = apple[t][1] = 0;
                apple_ = true;
                break ;
            }
        }
        
        if (!apple_)
		{
            struct node* tp = head;
            while (tp->link->link != NULL)
                tp = tp->link;
            free(tp->link);
            tp->link = NULL;
        }
        
        if (secondForDir[result] == 'D'){
            if (move_dir == 4)
                move_dir = 1;
            else
                move_dir += 1;
        }
        else if (secondForDir[result] == 'L'){
            if(move_dir == 1)
                move_dir = 4;
            else
                move_dir -= 1;
        }
    }
    cout << result;
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!