1R/워밍업문제

오늘의 문제

• BFS
• 넣기

참가자

• 15이원준, 박인서, 곽정흠

코드(DFS와 BFS)

15이원준

#include<iostream>
#include<queue>

using namespace std;

void DFS(int now);

int arr[1010][1010] = { 0, };
int visit[1010] = { 0, };
int N, M, V;
int visitNum = 0;

int main() {
	scanf("%d %d %d", &N, &M, &V);
	for (int i = 0; i< M; i++) {
		int tmp1, tmp2;
		scanf("%d %d", &tmp1, &tmp2);
		arr[tmp1][tmp2] = 1;
		arr[tmp2][tmp1] = 1;
	}
	DFS(V);
	cout << '\n';

	visitNum = 0;
	for (int i = 0; i<=N; i++) {
		visit[i] = 0;
	}
	queue<int> s;
	s.push(V);
	while (!s.empty() || visitNum != N) {
		int now = s.front();
		s.pop();
		printf("%d ", now);
		visitNum++;
		visit[now] = 1;
		for (int i = 0; i <= N; i++) {
			if (arr[now][i] == 1 && visit[i] == 0) {
				visit[i] = 1;
				s.push(i);
			}
		}
	}
}

void DFS(int now) {
	printf("%d ", now);
	if (visitNum == N) {
		return;
	}
	visitNum++;
	visit[now] = 1;
	for (int i = 0; i<=N; i++) {
		if (arr[now][i] == 1 && visit[i] == 0) {
			DFS(i);
		}
	}
}

박인서

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
 
std::vector<int> a[1001];
bool visit[1001] = { false, };
 
void dfs(int s, int n) {
    visit[s] = true;
    printf("%d ", s);
 
    for (int i = 0; i < a[s].size(); i++) {
        if (!visit[a[s][i]]) dfs(a[s][i], n);
    }
}
 
void bfs(int s, int n) {
    std::queue<int> q;
 
    for (int i = 1; i <= n; i++)
        visit[i] = false;
    q.push(s);
    visit[s] = true;
 
    for (int i = 0; !q.empty(); i++) {
        int qf = q.front();
        for (int j = 0; j < a[qf].size(); j++) {
            if (!visit[a[qf][j]]) {
                q.push(a[qf][j]);
                visit[a[qf][j]] = true;
            }
        }
        printf("%d ", q.front());
        q.pop();
    }
}
 
int main()
{
    int n, m, v;
    scanf("%d %d %d", &n, &m, &v);
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
 
    for (int i = 1; i <= n; i++)
        std::sort(a[i].begin(),a[i].end());
 
    dfs(v, n);
    printf("\n");
    bfs(v, n);
 
    return 0;
}

곽정흠

백준에서는 런타임오류란다 비주얼스튜디오는 잘 되는데..

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

int pop();
void push(int tmp);

int get();
void put(int tmp);

int stack[100];
int top, bottom;

int queue[100];
int front, rear;


int main(void) {
	int** graph;
	int n, m, v;
	int popTmp;
	int getTmp;

	scanf("%d%d%d", &n, &m, &v);

	graph = (int**)malloc(sizeof(int*)*(n + 1));
	for (int i = 0; i < n; i++) {
		graph[i + 1] = (int*)malloc(sizeof(int)*(n + 1));
		for (int j = 0; j < n; j++) {
			graph[i + 1][j + 1] = 0;
		}
	}

	for (int i = 0; i < m; i++) {
		int tmp1, tmp2;
		scanf("%d%d", &tmp1, &tmp2);
		graph[tmp1][tmp2] = 1;
		graph[tmp2][tmp1] = 1;
	}

	//dfs
	top = -1;
	bottom = 0;

	push(v);
	while (top != n - 2) {
		int j, test;
		popTmp = pop();
		printf("%d ", popTmp);
		j = popTmp;
		for (int i = 0; i < n; i++) {
			test = 0;
			for (int k = 0; k <= top; k++) {
				if (stack[k] == i + 1) {
					test = 1;
					break;
				}
			}
			if (graph[j][i + 1] == 1 && test == 0) {
				j = i + 1;
				printf("%d ", j);
				push(j);
				i = 0;
			}
		}
	}

	printf("\n");

	//bfs
	front = 0;
	rear = 0;

	put(v);
	while (front != rear) {
		getTmp = get();
		printf("%d ", getTmp);
		for (int i = 0; i < n; i++) {
			if (graph[getTmp][i + 1] == 1) {
				put(i + 1);
			}
		}
	}

	return 0;
}

int pop() {
	return stack[top--];
}

void push(int tmp) {
	for (int i = 0; i < top; i++) {
		if (stack[i] == tmp)
			return;
	}
	stack[++top] = tmp;
}

int get() {
	return queue[front++];
}

void put(int tmp) {
	for (int i = 0; i < rear; i++) {
		if (queue[i] == tmp)
			return;
	}
	queue[rear++] = tmp;
}

코드(상자 넣기)

15이원준

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

int main(){
  int N, max;
  vector<int> vec;
  vector<int> num;
  scanf("%d", &N);
  num.resize(N);
  for(int i = 0; i < N; i++){
    int temp;
    scanf("%d", &temp);
    vec.push_back(temp);
    max = 0;
    for(int j = 0; j < i; j++){
      if(num[j] > max && vec[j] < temp){
        max = num[j];
      }
    }
    num[i] = max + 1;
  }
  max = 0;
  for(int i = 0; i<N; i++){
    if(num[i] > max){
      max = num[i];
    }
  }
  printf("%d\n", max);
}

박인서

#include <iostream>
  
int a[1001],dp[1001];
  
int main()
{
        int n,i,j,max=0;
        //입력
        std::cin>>n;
        for(i=0;i<n;i++) std::cin>>a[i];
        //dp strat
        for(i=0;i<n;i++)
        {
                 for(j=0;j<i;j++)
                 {
                         if(a[j]<a[i] && dp[j]>=dp[i]) dp[i]=dp[j]+1;
                 }
                 if(dp[i]==0) dp[i]++;
                if(dp[i]>max) max=dp[i];
        }
        //출력
        std::cout<<max<<'\n';
        return 0;
}

곽정흠

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

typedef struct {
	int size;
	int canPut;
}box;

int main() {
	int num;
	box* boxes;
	int maxCanPut = 0; //현재까지 최대

	scanf("%d", &num);

	boxes = (box*)malloc(sizeof(box)*num);

	for (int i = 0; i < num; i++) {
		scanf("%d", &((boxes + i)->size));
	}

	for (int idx = 0; idx < num; idx++) {
		maxCanPut = 0;
		for (int i = 0; i < idx; i++) {
			if ((boxes + i)->size < (boxes + idx)->size) {
				if (maxCanPut < (boxes + i)->canPut) {
					maxCanPut = (boxes + i)->canPut;
				}
			}
		}
		(boxes + idx)->canPut = maxCanPut + 1;
	}

	maxCanPut = boxes->canPut;
	for (int i = 1; i < num; i++) {
		if ((boxes + i)->canPut > maxCanPut) {
			maxCanPut = (boxes + i)->canPut;
		}
	}

	printf("%d", maxCanPut);

	return 0;
}

아이디어

박인서

 * DFS와 BFS : DFS는 재귀 이용, BFS는 큐 이용
 * 상자 넣기 : dp[i]는 그 상자 기준 가장 많은 상자를 넣을 수 있는 가짓수입니다. 이것을 이용하여 계속 DP로 풀어나가면 됩니다.