일단 flow를 돌려서 정답을 하나 구해놓습니다.

그 다음에 해야할 일은?

flow 그래프가 유지되면서

a[i][j] == 1 이 최대한 늦게 등장하도록 흐름을 바꾸는 작업을 해야하는 거겠죠?

그럼 일단 if(a[i][j] == 1) 인 어떤 애에 대해서, 얘가 a[i][j] = 0이 되도록 바꿀 수 있는지를 알아보는 부분을 추가해야 합니다.

위의 그림은 a[s][e] = 1인 상황인데

얘를 어떻게 어떻게 빨간 선같은 경로를 잘 찾아서

flow는 똑같지만 a[s][e] = 0 이 되도록 만들 수 있습니다.

하도 옛날에 짜서 기억이 잘 안나는데...

저 사전순으로 앞서게 만들어주는 빨간 경로를 찾는게 아마 O(n^3)?O(n^2)? 쯤 걸릴거같고요

이를 n*n가지 애들에 대해 반복하면 (저 빨간 경로를 찾는 경우가 생각보다 많지 않아서) 시간내에 답이 나오게 됩니다....

뭐 추가적으로 한줄 적자면..

이 문제 같은 경우에는...사전순으로 가장 앞서는걸 한번에 뙇! 찾기보단..."현재 상황"보다 사전순으로 앞선거 "하나"만 대충 찾고, 이 작업을우다다닥 반복하다보면 사전순으로 가장 앞선 답이 딱 하고 나올것입니다... 이런 식으로 생각하면 코딩이 약간 더 쉬워질게용ㅋㅋㅋ

감사합니다! 해볼게요

@pichulia

간신히 뚫었습니다 감사합니다!