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 <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;
}

아이디어

박인서

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