코드가 너무 길어서...

팁만 드릴게요..

만약 x라는 건물을 건설하는데

x라는 건물을 만드는데 필요한 하위 건물중 가장 오래 걸리는 시간+지금 건물 짓는 시간을 계산 해주고,

이걸 반복하면서 최종적으로 x라는 건물의 시간이 나올때까지 반복하는데,

여기서 시간초과가 나지 않으려면,

필요한 건물의 시간이 나올때까지 그 건물의 하위 건물들을 짓는데 걸리는 시간을 저장해주어야 합니다.

왜냐하면, 저장을 해놓으면 또 다시 그 건물의 시간을 계산할 필요가 없기 때문입니다.

결론은 x를 구하기 위해서 x의 하위 건물의 시간+x건물을 짓는 시간을 구하고... x의 하위 건물의 시간을 구하려면 그 x의 하위건물의 하위건물.....

그렇게 했습니다. ㅠㅠ

119 : addTime[i] = (addTime[i] < addTime[stNode - 1] + pTime[stNode - 1]) ? addTime[stNode - 1] + pTime[stNode - 1] : addTime[i];

이부분이 그 부분인데 addTime 배열에 계속 누적 시간을 더해주면서 다음 건물에는 현재까지 누적시간+ 현재건물시간 을 구해서 다음 건물에 저장하고 했습니다.

흑.

언어가 C++ 이면

Queue를 직접 구현하지 않고 STL을 사용하시는것이 좋습니다.

그러면 다른사람이 소스를 이해하기도 쉽기 때문에 답변을 얻기도 쉽겠죠..

시간초과가 나는 이유는 다름이 아니라

while (now != -1) {

이 반복문을 빠져나가지 못해서인거 같네요....

arrIndegree 배열을 만들어놓고 제대로 사용을 안하고있네요. 검토해보시길....

코드를 몇가지 수정해서 맞았습니다를 받았습니다.

자료를 new delete를 실시간으로 한다고 해서 그렇게까지 느려지진 않나보네요

1. arrIndegree 배열 사용하기

for (int i = 0; i < line; i++) { //배열에 삽입

cin >> in >> out;

arrADJ[in - 1][out - 1] = 1;

arrIndegree[out-1]++;

}

아마 이게 원래 사용하고싶었던 arrIndegree 배열의 사용법일 것입니다....

자 이렇게하면 i번 노드로 들어오는 edge의 개수가(=arr[i]로 in 하는 선의 degree가) 저 arrIndegree에 저장되겠죠

2. 시작지점이 한군데가 아닐 수 있다

지금은 findFirst 뭐시기로 시작노드를 탐색하고 계시는데

시작노드가 한군데가 아닐 수 있음에 주의해야합니다.

뭐 대충 간단하게 예를 들자면

3

1 100000 1

1 3

2 3

3

이런 녀석이 있겠네요... findFirst 뭐시기로 풀면 2라고 출력될겁니다... 정답은 100001인데...

저는 이 부분을 calTime 함수 내부에서 처리했습니다.

for(int i=0; i<node; i++)

{

if(arrIndegree[i] == 0)

enQueue(i+1);

}

int now = deQueue();

arrIndegree[i] 가 0 이라는 것은, i로 들어오는 선의 개수가 0개라는 것을 의미하고, 즉 이런 애들은 모두 시작위치의 후보가 될 자격이 있는겁니다.

이 이후에는 뭐.... queue에서 하나씩 노드값을 꺼내서 사용하던 방식대로 쭉 풀어나가면 됩니다..

아 그리고 arrIndegree[]의 사용방법이 바뀌었으니

while(now != -1) 에 사용된 반복문에서 조건문을

for (int i = 0; i < node; i++) {

if (arrADJ[now - 1][i] == 1) {

arrIndegree[i] += -1;

if (arrIndegree[i] == 0) { enQueue(i+1); }

addTime[i] = ~~~~;

}

}

이런 식으로 바꾸는게 맞겠죠??

왜 그런지에 대한 자세한 설명은 생략합니다.ㅋㅋㅋ

아. 감사합니다 ㅠㅠ

arrIndegree 배열의 활용이 미숙해서 문제가 발생했었군요 ㅠㅠ;

더 많은 공부가 필요함을 다시 느끼고 갑니다.