vita_500   1년 전

이 문제는 위상정렬 알고리즘과 유향이아닌 무향 비순환 그래프로 풀수있습니다. 그 이유는 다음과 같습니다:

입력_

- vector<vector<int> > graph; 를 선언합니다.

- 입력을 인접배열로 받겠습니다. 그리고, graph[tmp].push_back(i); graph[i].push_back(tmp);를 하여 무향 비순환 그래프로 풀겠습니다.

- 또한 indegree[i]를 위의 단계에서 tmp의 개수만큼, increment 하겠습니다.

풀이 topology_sort() 함수내부에서_

- 진입차수를 사용하여 큐에 다음 정점을 삽입하겠습니다. 이때, 만약 진입차수가 0 이고, 해당 정점의 간선들 중에서 방문된 정점들에한하여 최대 시간을 구합니다. 이것으로, 다음 삽입할 정점의 시간을 매겨줍니다.

- 이렇게 되면, 무향 비순환 그래프이지만, 정점들의 진입차수로, 차례대로 작업하고. 무향 그래프의 요소인, 정점의 연결된 모든 간선들중 방문된 정점들만 쓰게하여, 문제에 필요한 답을 구해줍니다.

끝말_

- 제가 코린이라서 위의 내용이 타당하지 않을수 있지만, 유방향 그래프와 무방향 그래프의 명제로서 글을 작성해 봅니다.

- 문제의 알고리즘 분류에는 방향 그래프라고 명시되어 있습니다. 문제를 풀고나서 생각이나 적어 봅니다. 수고하십쇼.

zenith82114   1년 전

결국 indegree 기준으로 풀이가 진행될 텐데 그럼 그냥 DAG DP로 푸신 거 아닌가요

vita_500   1년 전

안녕하세요 @zenith82114, 스레드 달아주셔서 감사합니다.

그렇다는 것은,  DAG 그래프에서 이미 방문이된 것을 확인을 한다는것 자체가 DAG DP로 푼다는것이라면,

DAG에서 방문했다라는 것을 기준으로 풀면, 그것 또한 DAG DP아닌가요

 저는 indegree를 기준으로 undirected graph_

  • e = (a, b) = (b, a)
  • edge에 방향이 없어 (a,b)를 (b,a)로 나타내도 상관 없는 그래프를 의미한다.

로 풀었으니까, undirected acyclic graph DP아닌가요..?!

zenith82114   1년 전

저장을 양방향으로 하든 단방향으로 하든 indegree를 집계할 때 한쪽 방향만 고려하셨으면 그냥 통상적인 DAG DP를 하신 게 아니냐는 의미입니다.

vita_500   1년 전

indegree를 양방향으로도 집계할수가 있나요? 방향성이 있어야 indegree에 기여할수있는것 아닌가요?

저는 단지, 위상정렬을 쓸때, DAG로 풀어야 된다고 배웠는데, 풀고 나보니,  무방향 비순환 그래프로 풀어져있길래 궁금해서 올려봤습니다

zenith82114   1년 전

indegree라는 것이 방향성이 있어야 쓸 수 있는 말이란 걸 인지하고 계시면서 무방향 비순환 그래프로 풀었다고 말씀하시는 상황이 전혀 이해가 안 됩니다. 혹시 코드를 보여 주실 의향이 있으신지요

vita_500   1년 전


#94 ~ #95번줄의 코딩이 그래프를 무방향 그래프라고 선언하는것 아닌가요?

zenith82114   1년 전

양쪽으로 push_back을 했다고 해서 무조건 무방향 그래프인 게 아니라 본질을 봐야 할 것 같습니다.

결국 본질은 정방향 이웃들(#61)과 역방향 이웃들(#65)을 모두 빠르게 접근하고 싶어서 양쪽으로 저장을 한 것인데 정방향만 저장해 놓아도 충분히 풀 수 있습니다. 그리고 vis[graph[nxt][i]] > -1으로 필터링을 할 수 있는 이유도 주어지는 그래프가 DAG이기 때문입니다. 다시 말해 이 코드는 한쪽만 push_back하는 구현보다 메모리를 좀 더 쓰는 DAG DP일 뿐입니다.

vita_500   1년 전

제가 이해를 좀 한것같습니다.

입력을 받을시에 진입차수를 정방향 이웃들의 개수로서 매긴다는 의미 자체가 방향성을 부여 해주는것 이군요.

그리고, 역방향 이웃들의 여부를 확인하는것으로 DAG DP라는것 이구요.

감사합니다 !


그런데, 정방향만 저장해 놓고 풀어도 DAG DP 아닌가요?


zenith82114   1년 전

정방향만 저장해 놓으면 DAG DP가 아니라고 말씀드린 적은 없습니다. 오히려 DAG DP로 푼 사람들의 대부분이 정방향만 저장해서 풀었을 거라고 생각합니다.

vita_500   1년 전

그래프가 정방향이든 양방향이던 상관없이, 본질적으로 방향이 정해져있다는 말씀 이해했습니다. 감사합니다 !

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