dltkdgkr123   11달 전

(해당 문제는 #1005 ACM Craft와 비슷합니다. 문제 파악에 도움이 될까 싶어 말씀드립니다.)


1.

다익스트라(pq/greedy기반 구현) 탐색 시에는 큐에 pair(정점, 현재 가중치)를 넣어야합니다.

저는 해당 문제가 위상정렬임에도 pair(정점, 현재 가중치)를 사용해 탐색했습니다.

이후 큐에는 정점만 존재해도 탐색이 가능하다는 것을 깨달았고 큐에 가중치가 필요하지 않은 이유가 궁금해졌습니다.

.

.

다익스트라는 값에 따라 경로 자체가 변경되고, 그에 따라 가중치도 바뀌기 때문에 현재 가중치를 담아야한다.

위상정렬은 경로가 이미 굳어있기에, 경로 간 대소 비교만 수행하게 되므로 큐에 가중치는 별도로 필요하지 않다.

이렇게 생각했는데, 명쾌한 이유는 아니라고 생각합니다. 좀 더 근본적인? 명확한? 이유를 듣고싶습니다.

2.

이 문제가 '적절히' 변형된다고 했을 때, 위상정렬 기반임에도 pair(정점, 현재 가중치)를 이용한 탐색이 필요한 경우가 생기나요?

백준 문제가 이미 있다면 제시해주셔도 감사할 것 같습니다.

아래는 정점만 사용한 풀이 코드입니다.

zenith82114   11달 전

어떤 그래프가 위상 정렬이 가능하다는 것은 사이클이 없다는 것과 동치입니다. 그래프에 사이클이 없으면 최단경로를 다익스트라 대신 위상 정렬 DP로 구해도 무방하며 시간복잡도도 더 낮습니다. 대신 다익스트라는 사이클이 있어도 올바르게 동작합니다.

leeingyun96   11달 전

다익스트라는 구현 방식이 여러 가지인데 흔히 쓰는 게 1. pq에 그때그때 (총 거리, 인덱스)를 넣는 방식이고 2. pq에 모든 (총 거리=inf, 인덱스)를 넣고 그때그때 pq.edit(새로운 총 거리, 인덱스)를 하는 방식이 있습니다. 1이나 2나 pq.pop()하는 순간 그 head에 있는 건 동일하기 때문에 두 구현 모두 기본적으로 동일합니다.

위상정렬은 다익스트라의 2번과 마찬가지로 1. pq에 모든 (indgree=indegree, 인덱스)를 넣고 그때그때 pq.edit(indgree -= 1, 인덱스)를 해준다고 합시다. 사이클이 없는 이상 항상 pq.pop()을 할 때는 진입차수가 0인 정점이 나옵니다. 한편 2. 일반적인 구현으로 pq에 진입차수가 0인 정점만 넣는다고 합시다. 모두 0인 게 자명하기 때문에 그냥 인덱스만 넣어도 되겠죠. 그리고 1~n인 정점들은 어차피 언젠간 1씩 줄어들다가 0이 될 테고 결국 그때 pq안에 들어오게 될 겁니다. 이러면 결국 1이나 2나 똑같습니다. 단지 pq내에 진입차수 1~n인 게 들어있느냐 안 들어있느냐, pq내에 한 인덱스가 여러번 들어가냐 안 들어가냐의 차이겠죠.

좀 더 근본적으로는 'pq의 기준치가 0임이 자명하기 때문에 아예 생략하기 때문이다.', '서로 다른 총 거리들을 일일이 이진 힙 정렬할 필요없이, 새롭게 방문하고자 하는 child 정점이 자명하게 방문 가능하기 때문이다.' 같습니다.

dltkdgkr123   11달 전

새로운 시각과 자세한 설명주신 두 분 다 감사드립니다

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