개발자 톡
틀린 이유, 위상정렬 사용 안하고 푸는 방법
- 등록일
- 2024-09-18 20:16:19
- 조회수
- 117
- 작성자
- sj1226m
#include<iostream>
#include <map>
#include <vector>
using namespace std;
int main(int argc, char** argv)
{
int N, K;
cin >> N >> K;
int *ri = new int[N+1];
int *xi = new int[N+1];
int *res = new int[N+1];
// 초기화
for(int i = 0; i <= N; i++) {
res[i] = 0;
xi[i] = 1;
}
map<int, vector<int>> rb;
for(int i = 1; i <= N; i++) {
int r;
cin >> r; // 자식 수 입력
ri[i] = r;
vector<int> p;
for(int j = 0; j < r; j++) {
int tmp;
cin >> tmp;
p.push_back(tmp);
}
rb[i] = p;
}
for(int i = 0; i < K; i++) {
res[1]++;
int nxt = rb[1][xi[1]-1];
res[nxt]++;
while(rb.find(nxt) != rb.end() && ri[nxt] > 0) {
int srv = rb[nxt][xi[nxt]-1]; // 자식 노드의 현재 자식
res[srv]++;
xi[nxt] = (xi[nxt] % ri[nxt]) + 1;
nxt = srv;
}
xi[1] = (xi[1] % ri[1]) + 1;
}
for(int i = 1; i <= N; i++) {
cout << res[i] << " ";
}
delete[] ri;
delete[] xi;
delete[] res;
return 0;
}
위상 정렬 생각은 못하고 위의 코드처럼 풀었는데, 로직상 틀린 이유를 모르겠습니다..!