dydsj0920   1주 전

최대 유량을 구하는 문제에서 메인함수에서 MaximumFlow의 flow 함수를 호출했다는 가정하에

다음과 같이 1번 2번으로 나눠서 구조체를 짜봤는데요

저는 보통 1번처럼 vector<bool> check로 풀지만

2번처럼 vector<int> check와 새로 추가된 변수 step을 통해서

푸는 경우도 있더라구요. 제가 볼땐 차이가 없어 보이는데

어떤 문제에서는 2번으로 풀어야만 풀리는거 같은 문제도 있던 것 같은데..

어떤 차이가 있을까요?

appa   1주 전

질문에 대한 답을 드리자면, check 배열 초기화를 한다/안한다의 차이이기 때문에 시간복잡도 상 동일하며, 실제 프로그램 수행 시간에도 차이가 거의 없을 겁니다.

최대 유량을 구하는 알고리즘에서 spfa라는 함수명을 사용하셨는데, 사실 동작 방식을 보면 bfs라고 하는 게 옳다고 봅니다.

작성하신 알고리즘은 에드몬드 카프인데, bfs로 source로부터의 level graph를 구성한 후에 dfs를 이용하여 level이 증가하는 방향쪽으로 유량 경로를 탐색하는 디닉 알고리즘이 있습니다.

디닉을 사용하시면 에드몬드 카프보다 확실히 빠릅니다.

dydsj0920   1주 전

아 그런가요? 저는 벨만포드 알고리즘을 평균 시간복잡도를 좀더 빠르게 하기 위해 queue를 사용해서 저런식으로 구현한 방식이 Shortest Path faster algorithm 이라고 알고 있었는데요. Minimum Cost Maximum Flow에서만 bfs를 사용했을때 그것이 spfa로 불러지는 것인가요? 코드가 비슷해 딱히 구분해서 쓰지는 않았는데 좀 헷갈리네요.

appa   1주 전

특정 정점이 큐에 들어있는지를 보고, 큐에 넣는지 안넣는지를 결정하며 "단일 시작점 최단거리"를 계산하는 게 spfa입니다.
작성한 코드에서는 이미 방문한 노드는 방문하지 않으므로 bfs입니다.

dydsj0920   1주 전

답변 감사합니다!

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