cksdnwh   4년 전

BFS를 이용해서 최댓값을 노가다로 구했습니다.

처음에 이렇게 시도하면 안되겠구나 했는데, 이런 방법으로 성공하신 분들이 계시다고 하셔서 시도 해봤지만 실패..(시간초과)

코드를 지적해 주시던, 아니면 새로운 방법을 설명해 주시면 감사하겠습니다 ㅠㅠ초보좀 살려주세요


redball_var   4년 전

각 노드에서 bfs 돌려서 감염된 컴퓨터 수를 세는 방법으로 하신 것 같은데. 방법은 좋은 것같습니다.
코드가 복잡해서 오류를 직접 못 찾아드리지만,
제 생각에는 큐를 직접 구현하지 말고 stl 라이브러리 쓰시는게 좋을 것같아요.
저도 처음에는 직접 구현했는데, stl 써보니까 진짜 편하고 빠르게 구현할 수 있더군요.

cksdnwh   4년 전

넵 한 번 해보겠습니다

donghwashin   4년 전

신뢰하는 관계 M개를 net이라는 배열에 저장하셨고,
BFS 돌릴 때, 노드와 인접한 다른 노드를 찾기 위해서 M번씩 돌리시는 것 때문에 시간초과가 나는 것 같아요.
이럴 경우, BFS로 순회하는 노드 개수 X M (최대 100,000) 번 돌아가게 되는데요.

제 경우는 첨에 이 문제가 인접행렬을 쓰면 (A[10000][10000]) 메모리가 초과되어서
인접리스트를 써야겠다고 생각했고, STL 벡터 안쓰고 인접리스트 직접 만들려고
Node 클래스 정의해서 링크드리스트 기반으로 만들었는데, 그래도 시간초과...

그래서 그냥 벡터를 흉내낸 Dynamic Array를 직접 짠 다음, 그걸 기반으로 인접리스트를 만들어보자..
해서 시간초과 안나고 통과했습니다.

일단 M개의 신뢰하는 관계는 맨 처음 입력을 받을 때에, 한 번만 for문 돌면서
인접리스트 만들 때에만 써주시면 될 것 같구, 그 다음엔 인접리스트를 다뤄서 BFS 돌려보시는게 좋을 것 같아요.


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