개발자 톡

연습문제 톡 [21년 재직자 대회 예선] 로드 밸런서 트래픽 예측

틀린 이유, 위상정렬 사용 안하고 푸는 방법

등록일
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;

}


위상 정렬 생각은 못하고 위의 코드처럼 풀었는데, 로직상 틀린 이유를 모르겠습니다..!

#[21년_재직자_대회_예선]_로드_밸런서_트래픽_예측

이 카테고리의 톡 더보기