1R/워밍업문제

오늘의 문제

• BFS
• 넣기

참가자

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

코드(DFS와 BFS)

박인서

#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로 풀어나가면 됩니다.