N coding

고통받은 문제 어렵진 않은데 처음에 문제 잘못생각해서 겁나 어렵게 생각하다가 그래프 구성 못하고 가만히 있다가잘못생각했다는 걸 깨닫고 짰는데 또오 출력 바로 하려고 하다가 오지게 틀린 문제다.결과값 개수를 이미 들은 것중에 후보에 나온 애들의 개수를 세서 totalflow에서 빼서 출력했는데생각해보니 그러면 음수값이 나올수도 있어서... 당연히 틀리는 코드였다 ㅠ 사전순으로 출력이 아니라면 그냥 유량으로 쉽게 풀리는데사전순으로 출력이어서 mcmf로 풀었다.이미 들은 과목이면 반드시 포함시키는 게 이득이니까 그럴수 있게 가중치를 0으로 주었고그렇지 않은 과목이면 사전순으로 가중치를 주었다. 이분매칭으로 푸신 분도 있고, 그냥 유량으로 푸신 분도 있더라 123456789101112131415161718192..

나는 이분탐색 + 유량으로 풀었는데, 사실 가중치가 1이라서 그냥 이분매칭이다.주차장 문제랑 좀비 아포칼립스 문제를 짬뽕시킨 느낌이었다.아마 이분 매칭이면서 시간에 따른 정점 분리도 해서 그런 것 같다. 탈출구를 시간에 따라 정점 분리를 해줬다. 1초일때의 탈출구, 2초일때의 탈출구... 그리고 각각 1의 가중치로 sink와 연결빈칸인애들은 가중치 1로 source와 연결해준다. (이 때 가중치 = 유량은 사람을 뜻함)빈칸이나 벽인 애들은 굳이 해 줄 필요가 없다. 그리고 빈칸에서부터 탈출구까지의 거리를 구했다.이 때 나는 모든 빈칸을 출발지로 하고 bfs를 돌렸는데, 플로이드 워셜로 하신 분도 있고아니면 탈출구의 갯수가 (일반적으로) 더 적으니까 탈출구를 기준으로 bfs 돌려도 될거같다. 정점개수가 작..