ksjb2897   1년 전

에드몬드 카프 알고리즘으로 풀었습니다.

공부한대로 이해한대로 풀어봤는데, 처음에 25번줄에 dx != 1이 없었습니다. 그러니까 무한루프에 빠지더라구요. 찾아보니까 다른 노드에서 1번 노드로 가는 간선이 있을 수 있어서, bfs가 무한루프에 빠진다고 하더라구요. 

근데, 다른 사람들의 풀이 혹은 인터넷 풀이를 봤을 때는 dx != 1처리가 없을 뿐더러, 대부분의 source의 parent처리를 -1(제 코드에서는 0)로 유지하고 있습니다.. 

근데 왜 이 사람들의 코드는 무한루프에 빠지지 않고 제 코드는 무한루프에 빠지는지 도저히 이해가 안됩니다 ㅠㅠ 전 그래서 이 무한루프를 해결할 방법이 parent[source] = source로 처리한 후 뒤의 경로 추적의 로직을 살짝 바꾸거나, dx != 1처리를 하여 애초에 source로 오는 간선을 전부 무시하는 방법밖에 생각이 안나요. 이 처리들이 반드시 필요할 것 같은데, 왜 대부분의 다른 사람들의 코드들은 이러한 처리 없이 잘 돌아가는지 제 머리로 도저히 이해가안됩니다 ㅠㅠ 고수님들 도와주십쇼!!

okgo2026   1년 전

아래 소스 보시면 됩니다. 

ksjb2897   1년 전

주신 풀이는 이해가 됐습니다!

근데 제가 궁금한 점은 왜 다른 사람 풀이는 parent[source] 처리를 안해도 통과가 받는지 궁금한 것입니다 ㅠ

제가 처음에 올려드린 풀이는 통과를 받았어요! dx != 1이란 부분때문에 처음으로 다시 안돌아오게 되니깐요.

근데 다른 사람풀이는 처음으로 다시 안돌아오게 하는 장치가 없는데, 즉 parent[source] 처리도 없고, dx != 1 과 같은 돌아오지 않게 하는 처리도 없는데 왜 잘 돌아가는지 이해가 안됩니다.. ㅠ

zenith82114   1년 전

타인의 코드에 대해서 질문을 할 때도 코드를 직접 복사해서 가져오시거나 링크를 걸어주셔야 답변하기가 좋습니다. 치팅의 목적이 아니므로 당연히 문제가 되지 않습니다.

ksjb2897   1년 전

감사합니다.. 다시 질문해볼게요!

okgo2026   1년 전

현재 코드에서 루프가 돌만한 가능성이 2가지라고 생각합니다.

1) BFS : 근데 이건 VIS로 어차피 막으니까 상관없음 

2) 아래 코드 : 

ksjb2897   1년 전

아하..! 이해 드디어 됐습니다.. ㅠㅠ 다른 부분만 보고있었네요. 감사합니다!

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