nayuta9010   1년 전

시간초과가 나옵니다. ㅠㅠ

아직 자료구조 공부가 부족해서 그런지 문제점 찾기가 쉽지 않네요. 도움 부탁드립니다. ㅠㅠ

aaa   1년 전

코드가 너무 길어서...

팁만 드릴게요..

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

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

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

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

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

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

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

nayuta9010   1년 전

그렇게 했습니다. ㅠㅠ

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

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

흑.


yukariko   1년 전

언어가 C++ 이면

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

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

noeffserv   1년 전

뻘팁일수도 있지만..


이 문제는 1번 건물를 루트로 잡지 않고..

목표 건물을 루트로 잡고 거꾸로 탐색을(dfs or bfs) 하면서

최대값을 업뎃하면 풀기쉽습니다.



pichulia   1년 전

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

while (now != -1) {

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

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

pichulia   1년 전

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

자료를 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] = ~~~~;

}

}


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

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

nayuta9010   1년 전

아. 감사합니다 ㅠㅠ

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

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


댓글을 작성하려면 로그인해야 합니다.