Difference between r1.1 and the current
@@ -22,15 +22,255 @@
= 이민욱 =
== 미로 탐색 ==
{{{
== 후위표기식 ==
{{{
== 트리 순회 ==
{{{
= 정석우 =
== 미로 탐색 ==
{{{
(코드를 여기에)
#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);
}
}}}= 정석우 =
3.1. 미로 탐색 ¶
#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; }
3.2. 후위표기식 ¶
#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; }
3.3. 트리 순회 ¶
#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); }