연결 리스트를 이용한 알고리즘 문제 풀이

[연결 리스트]

1. 여러가지 연결 리스트 개념과 코드 : hello70825.tistory.com/158

2. 여러가지 연결 리스트를 이용한 알고리즘 문제 풀이: hello70825.tistory.com/159

3. 이중 연결 리스트 - 다항식의 연산(덧셈, 곱셈 : 구조체와 함수): hello70825.tistory.com/160

4. 이중 연결 리스트 - 다항식의 연산(덧셈, 곱셈 : 클래스와 operator): hello70825.tistory.com/219

5. 원형 연결 리스트 - 다항식의 연산(덧셈, 곱셈: 클래스와 operator, 반복자): hello70825.tistory.com/223

 

 

문제 모음 출처 - blog.naver.com/kks227/220781402507

1. 회전하는 큐(원형 이중 연결 리스트)

2. 풍선 터트리기(원형 이중 연결 리스트)

3. 조세푸스 문제(원형 연결 리스트)

4. 행운의 바퀴(원형 이중 연결 리스트)

5. 에디터(이중 연결 리스트 - 풀이: 원형 이중 연결 리스트)

6. 키로거(이중 연결 리스트 - 풀이: 원형 이중 연결 리스트)

7. 뱀(이중 연결 리스트)

 

문제풀이에 사용된 코드는 제가 만들어둔 원형 이중 연결 리스트의 코드(hello70825.tistory.com/158)를 변형하여 문제를 풀었습니다.

코드를 외우느라 문제를 풀 때마다 코드를 다 지우고 다시 쓰고 그래서 코드가 살짝살짝 다를수도 있습니다.

 

 

1. 회전하는 큐 - www.acmicpc.net/problem/1021

 

 

본문에 오른쪽으로 한 칸 이동, 왼쪽으로 한 칸 이동하는 기능이 있습니다.

이러면 원형 이중 연결 리스트로 풀 수 있다는 것을 알 수 있습니다.

 

여기서 2번 기능과 3번 기능은 연결 리스트의 head를 재설정 해줘야합니다.

 

그리고 원형 이중 연결 리스트는 이동할 수 있는 방향이 왼쪽(next), 오른쪽(prev) 밖에 없기 때문에 2번, 3번 연산의 최솟값은 현재 위치에서 오른쪽으로 계속 돌려서 목적지까지 도착했을때의 이동한 횟수와 현재 위치에서 왼쪽으로 계속 돌려서 목적지까지 도착했을때의 이동한 횟수중 작은 값을 골라 선택하면 됩니다. 이러면 계속 최솟값으로만 이동하게되니 최솟값들을 모두 합하면 최솟값이므로 답이 됩니다.

코드에서 이런 기능을 하는 함수는 find함수입니다.

 

문제에서는 아래와 같은 사진을 가정해서 왼쪽, 오른쪽 이동하면 저렇게 되는 것 같은데

제 코드는 이걸 반바퀴 회전시켜서 1이 맨 위로 가도록 생각하여 풀었습니다. 이렇게 풀면 2번기능이 오른쪽으로 이동하는 것이고, 3번 기능이 왼쪽으로 이동하는 것으로 생각하면 됩니다.

#include <bits/stdc++.h>
using namespace std;
 
class Node{
    friend class circular_doubly_linked_list;
private:
    int value;
    Node* next;
    Node* prev;
public:
    Node(int v, Node* n, Node* p):value(v),next(n),prev(p){}
};
 
class circular_doubly_linked_list{
private:
    Node* head;
    int size = 0;
public:
    circular_doubly_linked_list(){
        size = 0;
        head = nullptr;
    }
    void push_back(int v){
        Node* new_node = new Node(v, nullptr, nullptr);
        if(head == nullptr){
            head = new_node;
            new_node -> next = new_node;
            new_node -> prev = new_node;
        }
        else{
            new_node -> prev = head -> prev;
            new_node -> next = head;
            head -> prev -> next = new_node;
            head -> prev = new_node;
        }
        size++;
    }
 
    void erase(int v){
        Node* dest = head;
        while(dest -> value != v){
            dest = dest -> next;
        }
        dest -> prev -> next = dest -> next;
        dest -> next -> prev = dest -> prev;
        head = dest -> next;
        delete dest;
        size--;
    }
 
    int find(int target, int k){//k==1 오른쪽으로 회전, k==0 왼쪽으로 회전
        Node* dest = head;
        if (dest -> value == target) return 0;
        int z = 0;
        if(k==1)
            do{
                z++;
                dest = dest -> next;
                if(dest->value == target) return z;
            }while(dest != head);
        else
            do{
                z++;
                dest = dest -> prev;
                if(dest->value == target) return z;
            }while(dest != head);
    }
};
 
int main(){
    int n,m,A[51],ans=0;
 
    cin >> n >> m;
    for(int i=0; i<m; i++) cin >> A[i];
 
    circular_doubly_linked_list CDLL;
    for(int i=0; i<n; i++) CDLL.push_back(i+1);
 
    for(int i=0; i<m; i++){
        ans += min(CDLL.find(A[i],1),CDLL.find(A[i],0));
        CDLL.erase(A[i]);
    }
 
    cout << ans << endl;
 
    return 0;
}

 

 

 

2. 풍선 터트리기 - www.acmicpc.net/problem/2346

 

 

 

1번과 같이 원형 이중 연결 리스트를 이용하여 풀 수 있는 문제입니다.

이 문제는 풍선 번호를 출력시켜줘야하므로 풍선 안의 종이에 적혀 있는 수(value)를 저장할 뿐만 아니라 풍선의 번호(num)도 같이 저장시켜줘야합니다.

 

그리고 위 사진과 같이 8개의 풍선이 있다고하고, 풍선 안의 종이에 적혀있는 수가 양수라고하면 1->2->3->.. 로 이동해야하므로 다음 노드를 가리키는 next, 반대로 풍선 안의 종이에 적혀있는 수가 음수라고하면 1->8->7->...로 이동해야하므로 이전 노드를 가리키는 prev가 필요합니다.

 

이 문제에서 조심해야할 점은 풍선을 터뜨리고 나서 움직일 때, 지금 터뜨린 풍선을 빼고 숫자에 나온 종이대로 이동해야하는 것을 주의하며 구현해야합니다.

이게 무슨 말이냐면 만약 입력값으로

2
3 3

이런 값이 들어갔으면 1(터뜨림) -> 2 -> 1 -> 2 가 아닌 1(터뜨림) -> 2 -> 2 -> 2가 되게 구현해야한다는 것이죠

 

회전하는 큐보다 정답률이 낮은 이유가 이 부분 처리를 제대로 하지 않아서 그런 것 같습니다

 

#include <bits/stdc++.h>
using namespace std;
 
class Node{
    friend class circular_doubly_linked_list;
private:
    int value;
    int num;
    Node* next;
    Node* prev;
public:
    Node(int v, int t, Node* n, Node* p):value(v),num(t),next(n),prev(p){}
};
 
class circular_doubly_linked_list{
private:
    Node* head;
public:
    circular_doubly_linked_list(){
        head = nullptr;
    }
    void push_back(int v, int t){
        Node* new_node = new Node(v, t, nullptr, nullptr);
        if(head == nullptr){
            head = new_node;
            new_node -> next = new_node;
            new_node -> prev = new_node;
        }
        else{
            new_node -> prev = head -> prev;
            new_node -> next = head;
            head -> prev -> next = new_node;
            head -> prev = new_node;
        }
    }
 
    void erase(){
        int ans = head->value;
 
        cout << head -> num << " ";
        head -> prev -> next = head -> next;
        head -> next -> prev = head -> prev;
 
        Node* next_node = head;
        if(ans<0)
            for(int i=0; i<ans*(-1); i++)
                next_node = next_node -> prev;
        else
            for(int i=0; i<ans; i++)
                next_node = next_node -> next;
 
        delete head;
        head = next_node;
    }
 
};
 
int main(){
    int n,A[1001];
 
    cin >> n;
    for(int i=0; i<n; i++) cin >> A[i];
 
    circular_doubly_linked_list CDLL;
    for(int i=0; i<n; i++) CDLL.push_back(A[i],i+1);
 
    for(int i=0; i<n; i++) CDLL.erase();
 
    return 0;
}

위 코드에서는 erase함수를 변형 시켜놨는데, 먼저 터트리는 풍선의 숫자를 출력하고 위에 언급한 사항을 주의해서 풍선을 빼둔다음 앞뒤 노드를 연결시킨후에 value값만큼 이동하게 만들었습니다. 그리고 바로 다음 풍선을 터뜨릴 수 있도록 머리노드를 다음에 터뜨릴 풍선으로 설정해두었습니다.

 

 

 

3. 요세푸스 문제 - www.acmicpc.net/problem/1158

 

원형 연결 리스트로 풀어도 되고, 원형 이중 연결 리스트로 풀어도 되고 꼬리노드의 다음노드를 머리노드로 연결 시켜주기만 하면 풀 수 있는 문제입니다.

 

제 풀이는 원형 연결 리스트로 풀 때는 꼬리노드에서 출발하니까 꼬리 -> 1 -> 2 -> 3으로 K번만큼 이동하게 만들어주고, 3의 이전노드인 2를 꼬리노드로 설정하였습니다.

하지만 원형 이중 연결 리스트로 풀 때는 머리노드만 만들어놔서 1 -> 2 -> 3으로 K-1번만큼 이동하게 만들어주고, 3의 다음노드인 4를 머리노드로 설정해주었습니다.

 

이러면 for문을 하나씩만 적어도되서 코드가 간결해집니다.

 

- 원형 연결 리스트

 

#include <bits/stdc++.h>
using namespace std;
 
class Node{
    friend class circular_linked_list;
private:
    int value;
    Node *next;
public:
    Node(int v,Node *n):value(v),next(n){}
};
class circular_linked_list{
private:
    Node *tail;
public:
    circular_linked_list(){
        tail = nullptr;
    }
    void push_back(int k){
        Node *new_node = new Node(k,nullptr);
        if(tail==nullptr){
            tail = new_node;
            tail -> next = new_node;
        }
        else{
            new_node -> next = tail -> next;
            tail -> next = new_node;
            tail = new_node;
        }
    }
    void erase(int k, int z){
        Node *dest = tail;
        for(int i=0; i<k; i++){
            if(i==k-1) tail = dest;
            dest = dest -> next;
        }
 
        if(z==0)
            cout << dest -> value;
        else
            cout  << ", " << dest -> value;
 
        tail -> next = dest -> next;
        delete dest;
    }
};
 
int main(){
    int n, k;
    cin >> n >> k;
 
    circular_linked_list CLL;
 
    for(int i=0; i<n; i++) CLL.push_back(i+1);
 
    cout << "<";
    for(int i=0; i<n; i++) CLL.erase(k, i);
    cout << ">";
}

 

- 원형 이중 연결 리스트

 

class Node
{
    friend class circular_doubly_linked_list;
private:
    int value;
    Node *next;
    Node *prev;
public:
    Node(int v, Node *n, Node *p):value(v),next(n),prev(p){}
};
 
class circular_doubly_linked_list
{
private:
    Node* head;
public:
    circular_doubly_linked_list(){
        head = nullptr;
    }
    void push_back(int v){
        Node *new_node = new Node(v,nullptr,nullptr);
        if(head == nullptr){
            head = new_node;
            head -> next = head;
            head -> prev = head;
        }
        else{
            new_node -> next = head;
            new_node -> prev = head -> prev;
            head -> prev -> next = new_node;
            head -> prev = new_node;
        }
    }
 
    void erase(int t, int z){
        Node *dest = head;
        for(int i = 0; i<t-1; i++)
            dest = dest -> next;
 
        if(z==0)
            cout << dest -> value;
        else
            cout << ", " << dest -> value;
 
        head = dest -> next;
        dest -> prev -> next = dest -> next;
        dest -> next -> prev = dest -> prev;
        delete dest;
    }
};
 
int main()
{
    int k,n;
    cin >> k >> n;
 
    circular_doubly_linked_list CDLL;
 
    for(int i=0; i<k; i++)
        CDLL.push_back(i+1);
    cout << "<";
    for(int i=0; i<k; i++)
        CDLL.erase(n,i);
    cout << ">";
}

 

 

 

 

 

 

 

 

4. 행운의 바퀴 - www.acmicpc.net/problem/2840

 

이 문제는 화살표를 그대로 놓고 돌림판을 움직이는 문제이지만, 저는 돌림판을 그대로 놓고, 화살표를 움직인다고 가정하여 풀었습니다.

이러면 알파벳은 반시계방향로 이동해서 빈칸을 채우고, 출력할 때는 시계방향으로 출력하므로 원형 이중 연결 리스트로 풀 수 있어요.

 

이 문제에서 주의해야할 점은 돌림판에 같은 알파벳이 나오거나, 돌림판 어떤 칸에 두가지 이상의 알파벳이 올 수 있다면 느낌표(!)로 출력해야하는 것입니다.

그래서 전역변수로 같은 알파벳이 나오는지 확인하기 위한 배열 alphabet[27] = {0}과 느낌표를 출력을 해야할지 판단해주는 변수 err = false를 만듭니다.

 

예제가 하나 밖에 없으니 출력항목을 제대로 이해하지 못해서 정답률이 낮은 것 같습니다.

저는 돌림판 한 칸에 두가지 이상의 알파벳이 올 수 있다면 글자중 하나를 택할 수 없다고 판단하여 물음표를 출력하게 만들어서 틀렸네요.

#include <bits/stdc++.h>
using namespace std;
 
int alphabet[27] = {0};
bool err = false;
 
class Node{
    friend class circular_doubly_linked_list;
private:
    char value = '.';
    Node *next;
    Node *prev;
public:
    Node(char v, Node *n, Node *p)
    {
        value = v;
        next = n;
        prev = p;
    }
};
 
class circular_doubly_linked_list{
private:
    Node *head;
public:
    circular_doubly_linked_list(){
        head = nullptr;
    }
    void push_back(char x){
        Node *new_node = new Node(x, nullptr,nullptr);
        if(head == nullptr){
            head = new_node;
            head -> next = head;
            head -> prev = head;
        }
        else{
            new_node -> next = head;
            new_node -> prev = head -> prev;
            head -> prev -> next = new_node;
            head -> prev = new_node;
        }
    }
    void input(int k, char z){
        Node *dest = head;
        for(int i=0; i<k; i++) dest = dest -> prev;
        head = dest;
 
        if(head -> value == '.'){
            head -> value = z;
            alphabet[z-65] += 1;
            if(alphabet[z-65] > 1) err = true;
        }
        else if(head -> value != z) err = true;
    }
 
    void print(int k){
        Node *dest = head;
        for(int i=0; i<k; i++){
            if(dest -> value == '.')
                cout << "?";
            else
                cout << dest -> value;
            dest = dest -> next;
        }
    }
};
 
int main(){
    int n,k,a;
    char b;
    cin >> n >> k;
 
    circular_doubly_linked_list CDLL;
    for(int i=0; i<n; i++) CDLL.push_back('.');
 
 
    for(int i=0; i<k; i++){
        cin >> a >> b;
        CDLL.input(a,b);
    }
 
    if(err == true) cout << "!";
    else CDLL.print(n);
 
    return 0;
}
 
 

 

 

5. 에디터 - www.acmicpc.net/problem/1406

 

문제를 보면 왼쪽으로 이동(L), 오른쪽으로 이동(D), 삭제(B), 추가(P)가 있다. 이것을 통해 일단 이중 연결 리스트 기능이 필요하다는 것을 알 수 있습니다.

 

그리고 시간제한은 0.3초인데 연결 리스트의 단점은 Sequential access를 지원하기 때문에 삭제든, 추가든 for문을 이용하여 선형탐색을 합니다. 그래서 삭제/추가를 한 번 할때마다 O(N)의 시간이 걸려요

 

입력 부분을 살펴보면 첫 줄에 N개의 알파벳을 입력하므로 처음 노드의 최대 갯수는 100,000개가 됩니다.

그리고 M개줄에 걸쳐 명령어가 입력되는데 M의 최대값은 500,000입니다.. 이 M개줄 안에 추가/삭제 기능이 있는데 최악의 상황을 고려하면 M개의 줄에 전부 추가기능만 넣는 것이겠죠. 이러면 노드의 갯수는 최대 600,000개 이므로 대강 O(M^2)이 걸릴텐데 이 값은 1억을 훨씬 뛰어넘는 값으로 시간초과의 늪에서 벗어나지 못합니다.(실제로 for문을 이용한 코드를 넣어보면 시간초과가 나옵니다.)

 

그러므로 선형 탐색을 하지 않고 이중 연결 리스트에 현재 커서의 위치를 저장해주는 cursor 포인터 변수를 추가해줍니다.

이러면 추가/삭제를 하는데 전부 O(1)이 걸리므로 시간복잡도는 O(M)이 나옵니다.

이제 구현은 두가지로 나뉩니다.

 

하나는 아래 그림과 같이 문장 양 끝과 글자와 글자 사이에 공백을 넣은 다음, 그 부분을 커서를 지정하는 것이고,

나머지 하나는 아래 그림과 같이 글자를 커서로 지정하는 것입니다.

공백에 커서를 지정하는 경우는 문제에 나온 내용을 그대로 해석을 하여 구현하면 되기때문에 문제가 되지는 않습니다.(풀어보지는 않았어요)

 

근데 저는 글자를 커서로 지정하여 문제를 풀었는데, 이렇게 풀려면 문제를 약간 다르게 생각해야합니다.

 

사진을 보면서 아래 내용을 읽어보면 이해하기 쉽습니다.

 

B

수정 전: 커서 왼쪽에 있는 문자를 삭제함(커서가 문자의 맨 앞이면 무시됨)

수정 후: 커서에 있는 문자를 삭제함(커서가 머리노드에 있다면 무시됨) -> 머리노드에 관한 설명은 아래에 나옴

 

P $

수정 전: $라는 문자를 커서 왼쪽에 추가함

수정 후: $라는 문자를 커서가 있는 글자 오른쪽에 추가함

 

이제 첫줄에 나온 글자들을 미리 추가시켜줘야하므로 push_back함수, Cursor를 사용했으므로 커서를 이동시키는 move 함수, 값을 추가하는 insert함수, 값을 제거하는 erase함수, 마지막에 답을 출력하는 print함수를 만들면 됩니다.

 

저는 원형 이중 연결 리스트를 구현하고, 알파벳이 아닌 다른 값을 가지는 노드를 하나 추가해 머리노드를 고정시켜 만들었습니다.

원형 이중 연결 리스트가 이중 연결 리스트보다 좋은 점은 꼬리노드를 만들지 않아도 됩니다. head -> prev가 꼬리 노드이므로 만약 꼬리노드를 변경할 일이 있으면 head -> prev를 이용하여 값 변경만 하면 되고, 꼬리노드를 변수로 만들지 않았으므로 꼬리노드의 값을 주기적으로 업데이트하지 않아도 됩니다.

그리고 머리노드를 고정시키면, 머리노드의 값을 추가하거나 삭제를 하는게 아니라 머리노드의 다음값을 추가/삭제하므로 머리노드를 주기적으로 업데이트하지 않아도 됩니다.

 

위 내용을 그림으로 예시를 들자면 다음과 같습니다.

문제가 전혀 다른 문제가 된 것 같지만 안그래도 코드가 엄청 긴데 조금이라도 짧게 만들려면 이런식으로 변형을 많이 해야했습니다.

이 방식으로 코드를 짠다면 주의해야할 점은 코드가 값이 고정된 머리노드 중심으로 돌아가므로 erase함수 구현시 머리노드를 삭제하지 않도록 해야합니다.

 

그래서 나온게 아래 코드입니다.

#include <bits/stdc++.h>
using namespace std;
 
class Node{
    friend class circular_doubly_linked_list;
private:
    char value;
    Node *next;
    Node *prev;
public:
    Node(char v, Node *n, Node *p):value(v),next(n),prev(p){}
};
 
class circular_doubly_linked_list{
private:
    Node *head;
    Node *cursor;
public:
    circular_doubly_linked_list(){
        head = nullptr;
        cursor = nullptr; //현재 커서의 위치
        push_back('$'); //head는 무조건 $
    }
    void push_back(char v){
        Node *new_node = new Node(v,nullptr,nullptr);
        if(head == nullptr){
            head = new_node;
            head -> next = head -> prev = head;
            cursor = head;
        }
        else{
            new_node -> prev = head -> prev;
            new_node -> next = head;
            head -> prev -> next = new_node;
            head -> prev = new_node;
            cursor = new_node;
        }
    }
    void move(char v){
        if(cursor != head && v == 'L')
            cursor = cursor -> prev;
        else if(cursor != head->prev && v == 'D')
            cursor = cursor -> next;
    }
    void insert(char v){
        Node *new_node = new Node(v,nullptr,nullptr);
 
        new_node -> prev = cursor;
        new_node -> next = cursor -> next;
        cursor -> next -> prev = new_node;
        cursor -> next = new_node;
 
        cursor = new_node;
    }
 
    void erase(){
        if(cursor != head){
            cursor -> prev -> next = cursor -> next;
            cursor -> next -> prev = cursor -> prev;
            cursor = cursor -> prev;
        }
    }
 
    void print(){
        Node *now = head;
        while(now -> next != head){
            now = now -> next;
            cout << now -> value;
        }
        cout << endl;
    }
};
 
int main(){
    string x;
    int n;
    char y;
    circular_doubly_linked_list CDLL;
 
    cin >> x;
    for(int i=0; i<x.size(); i++)
        CDLL.push_back(x[i]);
 
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> y;
        if(y == 'L' || y == 'D') CDLL.move(y);
        else if(y == 'B') CDLL.erase();
        else{
            cin >> y;
            CDLL.insert(y);
        }
    }
 
    CDLL.print();
 
    return 0;
}

 

 

 

6. 키로거 - www.acmicpc.net/problem/5397

 

 

위에 있는 에디터와 많이 비슷한 문제입니다.

에디터 문제에서 코드 좀 줄여보았습니다.

 

에디터 코드와 다른 점은 처음에 값이 '$'인 머리노드를 넣어야하는데, 이거 하나 넣자고 push_back함수를 구현하는 것보다 원형 이중 연결 리스트 선언시 바로 머리노드를 생성하도록 만들었습니다.

그리고 에디터 코드 erase함수에 노드를 빼두기만하고 삭제를 안시켜서 tmp노드와 delete함수를 추가했습니다.

 

에디터 문제에 문제 풀이를 다해놨으니 에디터 풀이를 보면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
class Node{
    friend class circular_doubly_linked_list;
private:
    char value;
    Node *next;
    Node *prev;
public:
    Node(char v, Node *n, Node *p):value(v),next(n),prev(p){};
};
 
class circular_doubly_linked_list{
private:
    Node *head;
    Node *cursor;
public:
    circular_doubly_linked_list(){
        Node *new_node = new Node('$',nullptr,nullptr);
        head = cursor = new_node;
        head -> next = head -> prev = new_node;
    }
    void move(char z){
        if(z == '<' && cursor != head)
            cursor = cursor -> prev;
        else if(z == '>' && cursor != head -> prev)
            cursor = cursor -> next;
    }
    void insert(char v){
        Node *new_node = new Node(v, cursor->next, cursor);
        cursor -> next -> prev = new_node;
        cursor -> next = new_node;
        cursor = new_node;
        }
 
    void erase(){
        Node *tmp = cursor -> prev;
        if(cursor != head) {
            cursor->prev->next = cursor->next;
            cursor->next->prev = cursor->prev;
 
            delete cursor;
            cursor = tmp;
        }
    }
 
    void print(){
        Node *dest = head;
        while(dest -> next != head){
            dest = dest -> next;
            cout << dest -> value;
        }
        cout << endl;
    }
};
 
int main(){
    int t;
    cin >> t;
 
    for(int i=0; i<t; i++){
        string x;
        circular_doubly_linked_list CDLL;
 
        cin >> x;
        for(int j=0; j<x.size(); j++){
            if(x[j] == '<' || x[j] == '>') CDLL.move(x[j]);
            else if(x[j] == '-') CDLL.erase();
            else CDLL.insert(x[j]);
        }
 
        CDLL.print();
    }
    
    return 0;
}

 

 

 

 

 

7. 뱀 - www.acmicpc.net/problem/3190

 

 

일단 뱀을 연결 리스트로 구현시켜야하므로 각 노드안에 있는 값은 뱀의 현재 위치인 (x, y)와 다음노드(next), 이전노드(prev)가 필요합니다.

 

그다음 뱀이 사과가 있는 곳으로 이동할 때와 사과가 없는 빈공간을 이동할 때로 나눠서 살펴봅시다

 

먼저 뱀이 사과를 먹을 때를 살펴보면, 본문에서 뱀의 꼬리는 가만히 놔두고 머리만 이동시키라고 나와있습니다. 이말은 머리노드를 한 칸 늘려주어 늘린 칸을 머리노드로 변경시켜주면 된다는 소리입니다.

 

그리고 뱀이 사과가 없는 빈공간이 있는 곳에 뱀을 이동시킬때, 여기서 나는 이중 연결 리스트를 만들어서 구현하였습니다. 이건 그냥 연결리스트를 만들어서 풀 수도 있어요.

 

 

만약 이중 연결 리스트가 아닌 연결 리스트로 풀려면 뱀을 이동시킬 때, 머리노드에서 시작하여 꼬리노드까지 순차적으로 한 칸씩 이동시켜야하므로 위 그림과 같은 상황이 나옵니다.

그런데 뱀이 움직인다면 이렇게 B노드는 A노드의 이전 위치의 데이터를 가지고 이동해야하는데, A노드는 이미 움직여서 데이터가 변경된 후이므로 B노드가 이동하려면 뱀이 움직이기전에 뱀의 각 노드의 위치를 저장해둬야 합니다.

 

 

하지만 꼬리노드에서 시작하여 머리노드까지 순차적으로 한 칸씩 이동하면 어떻게 될까요?

먼저 꼬리노드부터 움직인다면 꼬리노드는 움직이기전 B노드의 위치데이터를 가지고 이동해야하는데, B노드는 아직 이동하지 않았으므로 B노드의 위치를 그대로 사용할 수 있습니다.

이제 B노드가 움직일 차례인데 B노드도 꼬리노드를 움직였을 때처럼 움직이기전 A노드의 위치데이터를 가지고 이동해야하는데, A노드는 아직 이동하지 않았으므로 A노드의 위치를 그대로 사용하여 (0,2)로 이동할 수 있습니다.

 

 

A노드도 마찬가지 방법으로 머리노드의 데이터를 이용하여 움직이고, 머리노드는 뱀의 머리 방향에 맞게 움직입니다.

 

이렇게 꼬리노드부터 시작해서 머리노드까지 한 칸씩 이동하면 원래 뱀이 가지고 있는 각 노드의 위치데이터가 없어도 움직일 수 있기때문에 공간을 낭비하지 않습니다. 이래서 저는 이중 연결 리스트를 사용하였습니다.

 

이제 뱀의 작동방식을 알아냈으므로 구현을 해야하는데, 구현에 사용하는 변수가 좀 많습니다. 아래는 전역으로 사용하는 변수입니다.

• t: 뱀이 몇초까지 움직이는지 필요한 변수. 출력에 쓰이는 변수입니다.
• m: 맵에 뱀이 어느 칸을 차지하고 있는지 필요한 배열. 뱀의 머리가 뱀의 몸통에 부딪치면 게임 오버이기 때문에 필요합니다. m[x][y] = 1이면 뱀이 차지하고 있는 칸이고, m[x][y] = 0이면 빈공간입니다.
• apple: 맵에 사과가 어디있는지 확인하는 변수. 이것은 m[x][y] = 2로 작성해서 m에 합쳐도 됩니다.
• nxny와 dir: 뱀의 머리가 어느방향인지, 뱀이 머리를 회전시키면 움직일때 어느방향으로 이동해야하는지 설정해주는 변수들입니다.
• q(queue), p(pair): 큐에 뱀의 방향 변환 정보를 넣어줍니다. 입력값이 <int, char>로 되어있기 때문에 pair로 만들어줘서 큐에 넣어줍니다.

다음은 뱀이 움직일 때 필요한 변수들입니다.

• nx와 ny: 뱀의 머리가 다음에 이동할 곳을 미리 계산해두는 변수입니다. 뱀의 머리가 맵 밖으로 나가는지, 뱀의 머리가 이동할 곳의 위치에 뱀의 몸통이 있는지(문제에서 뱀의 머리를 늘려 뱀의 머리를 다음칸에 위치시킨다고 나와있음), 뱀의 머리가 사과가 있는 곳인지 여부를 확인해줘야합니다.
• p와 nt, nd: p는 위에 설명한 뱀의 방향 변환 정보인데, 이것을 queue에서 뺍니다. 그리고 int형 값은 nt에, char형 값은 nd에 저장시키고, 뱀이 현재까지 움직인 시간인 t와 뱀의 머리방향이 바뀌는 시간인 nt가 같은 값이되면 뱀의 머리 방향 변수인 dir의 값을 변경시켜줍니다.

이걸 전부 코드로 짜면 아래와 같은 코드가 나옵니다.

#include <bits/stdc++.h>
using namespace std;
int t = 0;
int m[101][101] = {0};
int apple[101][101] = {0};
int nxny[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
int dir = 0;
pair<int, char>p;
queue<pair<int, char>> q;
 
 
class Node{
    friend class doubly_linked_list;
public:
    int x;
    int y;
    Node *next;
    Node *prev;
    Node(int x, int y, Node *n,Node *p):x(x),y(y),next(n),prev(p){};
};
 
class doubly_linked_list{
public:
    Node *head;
    Node *tail;
    doubly_linked_list(){
        Node *new_node = new Node(0,0,nullptr,nullptr);
        head = tail = new_node;
        m[0][0] = 1;
    }
    void move(){
        Node *dest = tail;
        m[tail->x][tail->y] = 0;
        do{
            if(dest == head){
                dest -> x = dest -> x + nxny[dir][0];
                dest -> y = dest -> y + nxny[dir][1];
            }
            else {
                dest-> x = dest-> prev -> x;
                dest-> y = dest-> prev -> y;
            }
            m[dest->x][dest->y] = 1;
            dest = dest -> prev;
        }while(dest != nullptr);
    }
 
    void eat_apple(int x, int y){
        Node *new_node = new Node(x,y,nullptr,nullptr);
        new_node -> next = head;
        head -> prev = new_node;
        head = new_node;
        m[x][y] = 1;
        apple[x][y] = 0;
    }
};
 
int main(){
    int n,k,x,y,l;
    char a;
 
    doubly_linked_list DLL;
 
    cin >> n;
    cin >> k;
    for(int i=0; i<k; i++){
        cin >> x >> y;
        apple[x-1][y-1] = 1;
    }
    cin >> l;
    for(int i=0; i<l; i++){
        cin >> x >> a;
        q.push(make_pair(x,a));
    }
    q.push(make_pair(99999,'D'));
 
    while(1){
        int nx, ny, nt;
        char nd;
        nx = DLL.head -> x + nxny[dir][0];
        ny = DLL.head -> y + nxny[dir][1];
        p = q.front();
        nt = p.first;
        nd = p.second;
 
        if(nx<0 || nx>=n || ny<0 || ny>=n || m[nx][ny]==1){
            cout << t+1 << endl;
            break;
        }
        else if(apple[nx][ny] == 1) DLL.eat_apple(nx,ny);
        else DLL.move();
 
        t++;
        if(t == nt){
            if(nd == 'D') dir = (dir+1)%4;
            else dir = (dir+3)%4;
            q.pop();
        }
    }
 
    return 0;
}