1516번 - 게임 개발
안녕하세요 @zenith82114, 스레드 달아주셔서 감사합니다.
그렇다는 것은, DAG 그래프에서 이미 방문이된 것을 확인을 한다는것 자체가 DAG DP로 푼다는것이라면,
DAG에서 방문했다라는 것을 기준으로 풀면, 그것 또한 DAG DP아닌가요
저는 indegree를 기준으로 undirected graph_
로 풀었으니까, undirected acyclic graph DP아닌가요..?!
indegree라는 것이 방향성이 있어야 쓸 수 있는 말이란 걸 인지하고 계시면서 무방향 비순환 그래프로 풀었다고 말씀하시는 상황이 전혀 이해가 안 됩니다. 혹시 코드를 보여 주실 의향이 있으신지요
양쪽으로 push_back을 했다고 해서 무조건 무방향 그래프인 게 아니라 본질을 봐야 할 것 같습니다.
결국 본질은 정방향 이웃들(#61)과 역방향 이웃들(#65)을 모두 빠르게 접근하고 싶어서 양쪽으로 저장을 한 것인데 정방향만 저장해 놓아도 충분히 풀 수 있습니다. 그리고 vis[graph[nxt][i]] > -1으로 필터링을 할 수 있는 이유도 주어지는 그래프가 DAG이기 때문입니다. 다시 말해 이 코드는 한쪽만 push_back하는 구현보다 메모리를 좀 더 쓰는 DAG DP일 뿐입니다.
댓글을 작성하려면 로그인해야 합니다.
vita_500 1년 전
이 문제는 위상정렬 알고리즘과 유향이아닌 무향 비순환 그래프로 풀수있습니다. 그 이유는 다음과 같습니다:
입력_
- vector<vector<int> > graph; 를 선언합니다.
- 입력을 인접배열로 받겠습니다. 그리고, graph[tmp].push_back(i); graph[i].push_back(tmp);를 하여 무향 비순환 그래프로 풀겠습니다.
- 또한 indegree[i]를 위의 단계에서 tmp의 개수만큼, increment 하겠습니다.
풀이 topology_sort() 함수내부에서_
- 진입차수를 사용하여 큐에 다음 정점을 삽입하겠습니다. 이때, 만약 진입차수가 0 이고, 해당 정점의 간선들 중에서 방문된 정점들에한하여 최대 시간을 구합니다. 이것으로, 다음 삽입할 정점의 시간을 매겨줍니다.
- 이렇게 되면, 무향 비순환 그래프이지만, 정점들의 진입차수로, 차례대로 작업하고. 무향 그래프의 요소인, 정점의 연결된 모든 간선들중 방문된 정점들만 쓰게하여, 문제에 필요한 답을 구해줍니다.
끝말_
- 제가 코린이라서 위의 내용이 타당하지 않을수 있지만, 유방향 그래프와 무방향 그래프의 명제로서 글을 작성해 봅니다.
- 문제의 알고리즘 분류에는 방향 그래프라고 명시되어 있습니다. 문제를 풀고나서 생각이나 적어 봅니다. 수고하십쇼.