새싹교실/2017/따라와반/과제방/자료구조/5회차

오늘의 실습 내용

• • 미로 탐색
  • 후위표기식
  • 트리 순회

신원준

미로 탐색

(코드를 여기에)

후위표기식

(코드를 여기에)

트리 순회

(코드를 여기에)

이민욱

미로 탐색

#include <iostream>
#include <queue>

using namespace std;

int Map[201][201];
int Visited[201][201];
int N, M;
queue<pair<int, int>> q ;

int check_range(pair<int,int> p){
    return p.first>-1&&p.first<N&&p.second>-1&&p.second<M;
}

int BFS(){
    pair<int, int> tmp;
    while(!q.empty()){
        tmp = q.front();
        q.pop();
        if(tmp.first==N-1&&tmp.second==M-1){
            return 1;
        }
        if(check_range(tmp)){
            if(Map[tmp.first][tmp.second]){
                Map[tmp.first][tmp.second]=0;
                q.push(make_pair(tmp.first-1,tmp.second));
                Visited[tmp.first-1][tmp.second]=Visited[tmp.first][tmp.second]+1;
                q.push(make_pair(tmp.first+1,tmp.second));
                Visited[tmp.first+1][tmp.second]=Visited[tmp.first][tmp.second]+1;
                q.push(make_pair(tmp.first,tmp.second+1));
                Visited[tmp.first][tmp.second-1]=Visited[tmp.first][tmp.second]+1;
                q.push(make_pair(tmp.first,tmp.second-1));
                Visited[tmp.first][tmp.second+1]=Visited[tmp.first][tmp.second]+1;
            }
        }
    }
    return 0;
}

int main() {
    int i, j;
    char c;
    scanf("%d %d", &N, &M);
    for(i=0;i<N;i++){
        for(j=0;j<M;j++){
            scanf(" %c", &c);
            if(c=='1') Map[i][j]=1;
        }
    }
    q.push(make_pair(0,0));
    Visited[0][0]=1;
    BFS();
    printf("%d\n", Visited[N-1][M-1]);
    return 0;
}

후위표기식

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

stack<char> Operator;
int checkPriority(char c){
    switch(c){
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '(':
            return 0;
    }
}
int main() {
    int i, k;
    char c;
    string str;
    getline(cin, str);
    k=str.length();
    for(i=0;i<k;i++) {
        c = str.at(i);
        switch (c) {
            case '+':
            case '-':
                while (!Operator.empty() && checkPriority(c)<=checkPriority(Operator.top())) {
                    printf("%c", Operator.top());
                    Operator.pop();
                }
                Operator.push(c);
                break;
            case '*':
            case '/':
                while (!Operator.empty() && checkPriority(c)<=checkPriority(Operator.top())) {
                    printf("%c", Operator.top());
                    Operator.pop();
                }
                Operator.push(c);
                break;
            case '(':
                Operator.push(c);

                break;
            case ')':
                while (!Operator.empty() && Operator.top() != '(') {
                    printf("%c", Operator.top());
                    Operator.pop();
                }
                if(!Operator.empty()){
                    Operator.pop();
                }
                break;
            default:
                printf("%c", c);
        }

    }
    while (!Operator.empty()) {
        printf("%c", Operator.top());
        Operator.pop();
    }
    return 0;
}

트리 순회

#include <stdio.h>
#include <stdlib.h>


typedef struct __Node{
    char Data;
    struct __Node* Left;
    struct __Node* Right;
} Node;

void SetNode(Node* node, char data);
Node* SearchNode(Node* tree, char data);
void SetLeft(Node* Root, Node* Child);
void SetRight(Node* Root, Node* Child);
void DestroyTree(Node* Root);

void preorder(Node* Root);
void Inorder(Node* Root);
void Postorder(Node* Root);

int main(){
    int i, j;
    int N;
    char Parent, Right, Left;
    Node *tmp, *tmp2;
    Node* Root = (Node*)malloc(sizeof(Node));


    SetNode(Root, 'A');

    scanf("%d", &N);

    for(i=0;i<N;i++){
        scanf(" %c", &Parent);
        tmp = SearchNode(Root, Parent);

        scanf(" %c", &Left);
        if(Left!='.') {
            tmp2=(Node*)malloc(sizeof(Node));
            SetNode(tmp2, Left);
            SetLeft(tmp, tmp2);
        }

        scanf(" %c", &Right);
        if(Right!='.') {
            tmp2=(Node*)malloc(sizeof(Node));
            SetNode(tmp2, Right);
            SetRight(tmp, tmp2);
        }
    }
    preorder(Root);
    printf("\n");

    Inorder(Root);
    printf("\n");

    Postorder(Root);
    printf("\n");

    DestroyTree(Root);

    return 0;
}


void SetNode(Node* node, char data){
    node->Left=NULL;
    node->Right=NULL;
    node->Data = data;
}
Node* SearchNode(Node* tree, char data){
    Node* tmp;
    if(tree==NULL) return NULL;
    if(tree->Data==data) return tree;
    tmp=SearchNode(tree->Left, data);
    if(tmp!=NULL) return tmp;
    tmp=SearchNode(tree->Right, data);
    if(tmp!=NULL) return tmp;
    return NULL;
}
void DestroyTree(Node* Root){
    if(Root==NULL) return;
    free(Root);
    DestroyTree(Root->Left);
    DestroyTree(Root->Right);
}
void SetLeft(Node* Root, Node* Child){
    Root->Left = Child;
}
void SetRight(Node* Root, Node* Child){
    Root->Right = Child;
}

void preorder(Node* Root){
    printf("%c", Root->Data);
    if(Root->Left!=NULL) {
        preorder(Root->Left);
    }
    if(Root->Right!=NULL) {
        preorder(Root->Right);
    }
}

void Inorder(Node* Root) {
    if(Root->Left!=NULL) {
        Inorder(Root->Left);
    }
    printf("%c", Root->Data);
    if(Root->Right!=NULL) {
        Inorder(Root->Right);
    }
}

void Postorder(Node* Root){
    if(Root->Left!=NULL) {
        Postorder(Root->Left);
    }
    if(Root->Right!=NULL) {
        Postorder(Root->Right);
    }
    printf("%c", Root->Data);
}

정석우

미로 탐색

(코드를 여기에)

후위표기식

(코드를 여기에)

트리 순회

(코드를 여기에)