3.1. 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);
}
}
}
3.2. 박인서 ¶
#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;
}
3.3. 곽정흠 ¶
백준에서는 런타임오류란다
#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;
}
4.1. 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);
}
4.2. 박인서 ¶
#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;
}
