Gidhub BE Developer

# BOJ - 장난감 조립

2018-02-04
goodGid

## Problem

Problem URL : 장난감 조립

``````#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된다.