simm4256   3달 전

제가 짠 알고리즘은 다음과 같습니다.


1) 그래프를 조건에 맞게 구현하되, 이중 연결 리스트로 구현한다. 각 노드의 check값은 0이다.

2) 입력받은 w를 기준으로 왼쪽에 해당하는 노드들(왼쪽 링크들에 연결된 모든 노드들)의 check값을 1로 바꾼다.

3) check된 노드 중 왼쪽 링크가 NULL인 노드들을 시작노드로 설정한다.

4) 시작노드들의 번호,시간 쌍들을 최소 힙에 push한다.

5) 힙을 pop하고, pop된 노드의 check값을 2로 바꾼다. (현재 시간에서 가장 빨리 완성할 수 있는 노드가 pop된다.) (여기서 pop된 노드는 그 시간에 완성된 건물이다.)

  5-1) pop한 노드의 오른쪽에 연결된 모든 노드중 check값이 0이아닌 노드를 검사한다. 이 때, 검사하는 노드의 왼쪽에 연결된 모든 노드의 check값이 2이면, 즉 해당 노드를 건설하기 위해 필요한 모든 건물을 지었다면, 그 노드를 힙에 push한다.

6) 번호가 w인 노드가 pop될때까지 5번을 반복한다.

7) w를 pop했을 때의 시간을 출력한다.



질문에 올라와있는 예제들 넣어봤는데, 반례는 못찾겠네요..


isangyoon   3달 전

O(n) 해법이 존재하는 문제입니다. 이중연결리스트까지 쓸 필요 없이 배열로 충분히 풀 수 있어요.

DFS 탐색을 활용하여 마지막 노드부터 처음노드로 오면서  cost의 최댓값을 찾아주시는 해법을 생각해보세요!

isangyoon   3달 전

아참, 그래프를 보이시는데로 추상화 하실 필요 없이,

1번 2번 3번 ... n번에 해당하는 cost로 그래프를 구성하시면 됩니다. 이중연결리스트까지 쓰시면서 구현하시면 너무 복잡하기만해서 구현하는 시간이 더 많이 걸리는데, 오히려 계륵같네요.

simm4256   3달 전

답변주신건 정말 감사합니다. 제시해주신 방법으로도 풀어봐야겠네요.

근데 제가 궁금한건 제 풀이에 어떤 문제점이 있는가여서... 틀린 점을 찾지 못하면 다른 풀이로 손이 가지 않을 것 같네요 ㅜㅜ

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