Gidhub BE Developer

BOJ - 장난감 조립

2018-02-04
goodGid

Problem

Problem URL : 장난감 조립

Screenshots of Problem Explain

Answer Code

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

vector<vector<int>> v;
queue<int> q;
int d[101][101]; // d is DP
int visit[101]; // v is Visit
int chk[101];

int main(){
    int n,m;
    cin >> n >> m;

    v.resize(n+1);
    while (m--) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        chk[a] ++ ;
        v[b].push_back(a);
        d[a][b] = c;        // a를 만들기 위해 b부품 c개 필요
    }
    for(int i=1; i<=n; i++){
        if(chk[i] == 0){
            visit[i] = 1;
            q.push(i);
        }
    }
    
    while (! q.empty()) {
        int top = q.front();
        q.pop();
        
        int size = (int) v[top].size();
        for(int i=0; i<size; i++){
            int nx = v[top][i];
            chk[nx] --;
            
            if(chk[nx] == 0){
                q.push(nx);
            }
            for(int j=1; j<=n && visit[top] != 1; j++){
                    d[nx][j] += ( d[top][j] * d[nx][top]);
            }
        }
    }
    
    for (int i=1; i<=n; i++) {
        if(d[n][i] != 0 && visit[i] == 1)
            printf("%d %d\n",i,d[n][i]);
    }
    
    return 0;
}



Wrong Code


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

vector<vector<int>> v;
queue<int> q;
int d[101][101]; // d is DP
int visit[101]; // v is Visit
int chk[101];

int main(){
    int n,m;
    cin >> n >> m;
    v.resize(n+1);
    while (m--) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        chk[a] = 1;
        v[b].push_back(a);
        d[a][b] = c;        // a를 만들기 위해 b부품 c개 필요
    }
    for(int i=1; i<=n; i++){
        if(chk[i] == 0){
            visit[i] = 1;
            q.push(i);
        }
    }
    
    while (! q.empty()) {
        int top = q.front();
        q.pop();
        
        int size = (int) v[top].size();
        for(int i=0; i<size; i++){
            int nx = v[top][i];
            
            if(visit[nx] == 0){
                visit[nx] = 1;
                q.push(nx);
            }
            for(int j=1; j<=n && chk[top] != 0; j++){
                d[nx][j] += ( d[top][j] * d[nx][top]);
            }
        }
    }
    
    for (int i=1; i<=n; i++) {
        if(d[n][i] != 0 && chk[i] == 0){
            printf("%d %d\n",i,d[n][i]);
        }
    }
    
    return 0;
}

Feed Back (18. 02. 04)

Anser Condition Code

if(nx > 0 && nx <=n && ny > 0 && ny <= m && map[nx][ny] != -1 && d[nx][ny] <= idg)
            dfs(nx,ny,idg+1);

Wrong Code

9
9
6 5 3
6 4 6
8 6 4
8 2 2
9 8 3
9 7 2
7 3 1
7 1 5
7 4 7
  • Input으로 넣고 [ nx == 9 && j == 4 ]일 때 Debug해보면 이유를 알것이다.

  • 1 2 3 4 5 7 8 6 9 순서로 Queue에 들어가는데
    이 때 8을 해결하기 위해선 d[6]값이 최신으로 Update되어 있어야한다.

  • 그런데 Indegree를 따지지 않고 Queue넣는 Wrong Code같은 경우에는 d[6]이 최신이 아닌 상태로 작업이 진행되기 때문에 잘못된 값으로 DP값이 Update된다.


Comments

Content