공부한대로 이해한대로 풀어봤는데, 처음에 25번줄에 dx != 1이 없었습니다. 그러니까 무한루프에 빠지더라구요. 찾아보니까 다른 노드에서 1번 노드로 가는 간선이 있을 수 있어서, bfs가 무한루프에 빠진다고 하더라구요.
근데, 다른 사람들의 풀이 혹은 인터넷 풀이를 봤을 때는 dx != 1처리가 없을 뿐더러, 대부분의 source의 parent처리를 -1(제 코드에서는 0)로 유지하고 있습니다..
근데 왜 이 사람들의 코드는 무한루프에 빠지지 않고 제 코드는 무한루프에 빠지는지 도저히 이해가 안됩니다 ㅠㅠ 전 그래서 이 무한루프를 해결할 방법이 parent[source] = source로 처리한 후 뒤의 경로 추적의 로직을 살짝 바꾸거나, dx != 1처리를 하여 애초에 source로 오는 간선을 전부 무시하는 방법밖에 생각이 안나요. 이 처리들이 반드시 필요할 것 같은데, 왜 대부분의 다른 사람들의 코드들은 이러한 처리 없이 잘 돌아가는지 제 머리로 도저히 이해가안됩니다 ㅠㅠ 고수님들 도와주십쇼!!
ksjb2897 1년 전
에드몬드 카프 알고리즘으로 풀었습니다.
공부한대로 이해한대로 풀어봤는데, 처음에 25번줄에 dx != 1이 없었습니다. 그러니까 무한루프에 빠지더라구요. 찾아보니까 다른 노드에서 1번 노드로 가는 간선이 있을 수 있어서, bfs가 무한루프에 빠진다고 하더라구요.
근데, 다른 사람들의 풀이 혹은 인터넷 풀이를 봤을 때는 dx != 1처리가 없을 뿐더러, 대부분의 source의 parent처리를 -1(제 코드에서는 0)로 유지하고 있습니다..
근데 왜 이 사람들의 코드는 무한루프에 빠지지 않고 제 코드는 무한루프에 빠지는지 도저히 이해가 안됩니다 ㅠㅠ 전 그래서 이 무한루프를 해결할 방법이 parent[source] = source로 처리한 후 뒤의 경로 추적의 로직을 살짝 바꾸거나, dx != 1처리를 하여 애초에 source로 오는 간선을 전부 무시하는 방법밖에 생각이 안나요. 이 처리들이 반드시 필요할 것 같은데, 왜 대부분의 다른 사람들의 코드들은 이러한 처리 없이 잘 돌아가는지 제 머리로 도저히 이해가안됩니다 ㅠㅠ 고수님들 도와주십쇼!!