[개인 공부] 거북이 프로그램

거북이 명령 프로그램 Turtle.zip

수업 과제로 있길래 만들어봤다.

// Example.mp4

// Turtle.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <Windows.h>
 
using namespace std;
 
#define MAX_LINE_LENGTH 100
 
void gotoxy(int x, int y)
{
    COORD Pos = { x, y };
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), Pos);
}
 
class Vector2 {
public:
    Vector2() { x = 0; y = 0; }
    Vector2(int x, int y) {
        this->x = x; this->y = y;
    }
 
    Vector2& operator+=(const Vector2& vector) {
        x += vector.x; y += vector.y;
        return (*this);
    }
 
    int x, y;
};
 
class Turtle {
public:
    void readFile(char *fileName) {
        ifstream commandFile;
        char command[MAX_LINE_LENGTH];
        
        init(); // 객체 초기화
 
        // 파일 읽기
        commandFile.open(fileName, ios::in);
        if (commandFile.fail()) {
            fprintf(stderr, "파일이 열리지 않습니다.\n");
            system("pause");
            exit(-1);
        }
 
        while (!commandFile.eof()) {
            commandFile.getline(command, MAX_LINE_LENGTH);
            commandList.push_back(command);
        }
 
        commandFile.close();
 
        // 계산
        compute(0, commandList.size() - 1);
    }
    void draw() {
        // 배열 생성 및 초기화
        size_t width = (arrSize[1] + -arrSize[3]) * 2 + 1, height = (arrSize[0] + -arrSize[2]) * 2 + 1; // * 2 : 간선과 정점, + 1 : 시작 점 포함
        char ***drawArr = createDrawArr(width, height);
        char *drawChar;
 
        pos = Vector2(-arrSize[3] * 2, -arrSize[2] * 2); // start = (Left, Down)
 
         // 배열에 그리기
        while (!dirQueue.empty()) {
            dirIndex = dirQueue.front();
            if (dirIndex % 2 == 0)    drawChar = "│"; // Up or Down
            else                    drawChar = "─"; // Right or Left
 
            pos += dirArr[dirIndex];
            drawArr[pos.y][pos.x] = drawChar;    // 간선 그리기
 
            pos += dirArr[dirIndex];
            drawArr[pos.y][pos.x] = "＊";        // 정점 그리기
            
            dirQueue.pop();
        }
 
        // 화면에 그리기
        for (int i = height - 1; i >= 0; i--) {
            for (int j = 0; j < width; j++)
                printf("%s", drawArr[i][j]);
            printf("\n");
        }
 
        destroyDrawArr(drawArr);
    }
    void sequenceDraw(unsigned int delay) {
        size_t width = (arrSize[1] + -arrSize[3]) * 2 + 1, height = (arrSize[0] + -arrSize[2]) * 2 + 1; // * 2 : 간선과 정점, + 1 : 시작 점 포함
 
        char *drawChar;
        pos = Vector2(-arrSize[3] * 2, -arrSize[2] * 2); // start = (Left, Down)
 
        while (!dirQueue.empty()) {
            dirIndex = dirQueue.front();
            if (dirIndex % 2 == 0)    drawChar = "│"; // Up or Down
            else                    drawChar = "─"; // Right or Left
 
            pos += dirArr[dirIndex];
            gotoxy(pos.x * 2, height - pos.y - 1);
            printf("%s", drawChar);    // 간선 그리기
            
            Sleep(delay);
 
            pos += dirArr[dirIndex];
            gotoxy(pos.x * 2, height - pos.y - 1);
            printf("%s", "＊");        // 정점 그리기
 
            dirQueue.pop();
 
            Sleep(delay);
        }
 
        gotoxy(0, height + 1);
    }
 
private:
    void init() {
        commandList.clear();
 
        dirQueue = queue<int>();
        dirIndex = 0;
        pos = Vector2(0, 0);
 
        memset(arrSize, 0, sizeof(int) * 4);
    }
 
    int classifyCommand(string command) {
        // 탭 제거
        int i, len = command.size();
        for (i = 0; i < len && command[i] == '\t'; i++);
 
        // 분류
        if (command[i] == 'r') {
            if (command[i + 1] == 'e')        return 0; // repeat
            else if (command[i + 1] == 'i')    return 2; // right
        }
        else if (command[i] == 'g')            return 1; // go
        else if (command[i] == 'l')            return 3; // left
 
        return -1;
    }
    void compute(int start, int end) {
        for (int i = start + 1; i < end; i++) {
            switch (classifyCommand(commandList[i])) {
            case 0: // repeat
                int repeatNum, tapNum, endTapNum, endLine;
                sscanf(commandList[i].c_str(), "%*s %d", &repeatNum); // 반복 횟수 가져오기
                
                // end 문자열 찾기
                for (tapNum = 0; commandList[i][tapNum] == '\t'; tapNum++);
                for (endLine = i + 1; i < end; endLine++) {
                    for (endTapNum = 0; commandList[endLine][endTapNum] == '\t'; endTapNum++);
                    if (endTapNum == tapNum) break;
                }
 
                if (commandList[endLine][endTapNum] != 'e') {
                    fprintf(stderr, "올바른 형식이 아닙니다.\n");
                    system("pause");
                    exit(-2);
                }
                
                for (int j = 0; j < repeatNum; j++)
                    compute(i, endLine);
                i = endLine;
                break;
            case 1: // go
                dirQueue.push(dirIndex);
 
                pos += dirArr[dirIndex];
                switch (dirIndex) {
                case 0: if (pos.y > arrSize[0]) arrSize[0] = pos.y; break; // Up 
                case 1: if (pos.x > arrSize[1]) arrSize[1] = pos.x; break; // Right
                case 2: if (pos.y < arrSize[2]) arrSize[2] = pos.y; break; // Down
                case 3: if (pos.x < arrSize[3]) arrSize[3] = pos.x; break; // Left
                }
                break;
            case 2: // right
                dirIndex = (++dirIndex % 4);
                break;
            case 3: // left
                if (--dirIndex < 0) dirIndex = 3;
                break;
            }
        }
    }
 
    char ***createDrawArr(size_t width, size_t height) {
        char ***drawArr;
 
        drawArr = new char **[height];
        for (int i = 0; i < height; i++) {
            drawArr[i] = new char *[width];
            for (int j = 0; j < width; j++)
                drawArr[i][j] = "　";
        }
 
        return drawArr;
    }
    void destroyDrawArr(char ***& drawArr) {
        if (drawArr != nullptr) {
            size_t height = (arrSize[0] + -arrSize[2]) * 2 + 1;
            for (int i = 0; i < height; i++)
                delete[] drawArr[i];
            delete[] drawArr;
 
            drawArr = nullptr;
        }
    }
 
private:
    const Vector2 dirArr[4] = { Vector2(0, 1), Vector2(1, 0), Vector2(0, -1), Vector2(-1, 0) }; // Up, Right, Down, Left
    
    vector<string> commandList;
 
    queue<int> dirQueue;
    int dirIndex;
    Vector2 pos;
 
    int arrSize[4]; // Up, Right, Down, Left
};
 
int main(int argc, char *argv[]) {
    Turtle turtle;
    char *fileName;
    
    if (argc <= 1) {
        fileName = "input.txt";
 
        system("cls");
 
        turtle.readFile(fileName);
        turtle.sequenceDraw(25);
 
        system("cls");
 
        turtle.readFile(fileName);
        turtle.draw();
 
        system("pause");
        return 1;
    }
 
    for (int i = 1; i < argc; i++) {
        fileName = argv[i];
 
        system("cls");
 
        turtle.readFile(fileName);
        turtle.sequenceDraw(25);
 
        system("cls");
 
        turtle.readFile(fileName);
        turtle.draw();
 
        system("pause");
    }
}

// 설명.txt

핵심 알고리즘은 Dynamic Programming(큰 문제를 작은 문제로 쪼개 해결하는 것)을 기초로 하였다.

제일 중요한 코드는 Turtle 클래스의 compute 함수다.

compute 함수는 commandList 배열에 들어있는 명령어들을 처리하여, dirQueue 에 dirArr의 index를 뜻하는 정수들을 넣어준다.

매개변수 start와 end는 처리할 commandList 배열의 시작과 끝을 말한다.

repeat 명령어의 처리는 반복문과 재귀함수를 이용했다.

0.program

1. go

2. repeat 3

3. go

4. right

5. end

6.end

위와 같이 입력예제가 있다고 가정해보자.

일단, 반복 횟수인 3을 추출한다

repeat와 end 사이에 있는 3-4번줄 명령어는 또 다른 코드라고 볼 수 있다.

따라서, compute(2, 5)를 호출하여 사이에 있는 명령어를 처리할 수 있다.

이를 3번 반복하기 위해서 다음과 같은 코드가 되게 한다.

int num = 3;

for (int i = 0; i < num; i++)

compute(2, 5);

이후 5번 줄까지의 명령어는 이미 처리되었기 때문에, 다음에 처리할 명령어의 줄을 6으로 설정해야 한다.

i = endLine;

위 코드가 해당 역할을 해준다.

실수했던 점은 repeat에 대응하는 end 문자열을 찾는 일이였다.

처음에는 맨아래서부터 tap의 길이를 무시하고 end를 찾아 올라왔었는데,

0. program

1. repeat 3

2. go

3. end

4. repeat 2

5. go

6. end

7. end

이런 코드가 있을 경우 제대로된 처리가 되지 않았다.

따라서, 기존에 했던 방법을 철회하고 해당 repeat 줄을 기점으로 차례대로 내려가면서 같은 tap의 길이이면서 end문자열이 있는 줄을 찾는 방식으로 프로그래밍 하였다.

위 예제의 경우 기존 코드는 1번줄 repeat에 6번줄 end를 대응시키는데, 변경시킨 코드의 경우 1번줄 repeat에 3번줄 end를 대응시킨다.

이로써 해당 문제를 해결하였다.