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