백준 9376 탈옥 (다익스트라, 0-1 BFS) - 아직 푸는중...

9376번: 탈옥

 

 

문제를 잘못이해한게 죄수가 탈옥을 하기 위한 최소의 경로를 찾는게 아니라 문을 최대한 적게 열고 나가야하는점이다.
즉 bfs로 최소 거리를 구한다해도 그 경로가 문을 많이 열었다면 정답이 아니다.

그럼 문을 최소로 여는 경로는 대체 뭐가 있을까?
1. dfs를 쫙 돌리면서 탈옥을 할 때 가장 문을 적게 열었던 경로를 기억하면 되지 않을까?
그 경로를 2번째 죄수가 탈옥할 때 어떤 문을 열어둘지 정하는거지.
근데 여기서 1번째 죄수의 경로를 기준으로 할 필요가 있을까?
2번째 죄수가 가장 문을 적게 나간 경로가 최적의 경로가 될 수도 있지 않을까?

근데, 문을 연 횟수가 똑같은 경로가 여러개 있다고 치면 어떤 경로로 가야 두 죄수 모두 만족되는 경로라고 할 수 있을까?
그 경로들의 후보를 모두 저장해서 모두 돌려봐? 그건 진짜 아닌거같은데

그러면 탈옥이 되는 그 위치가 있을꺼 아니야. board 바깥쪽 1칸씩 연장된 부분.

와 찾았다 
1. 1번이 탈옥하는데 3, 2번이 1번 나간 경로 후보들 중에 최소값은 8이라면 1,2번이 1번의 최적경로로 나가는 방법은 11
2. 2번이 탈옥하는데 2, 1번이 2번 나간 경로 후보들 중 최소값이 6이라고 하면 1,2번이 2번의 최적의 경로로 나가는 방법은 8
지금까지 1,2번 각각의 최소값으로 된 탈옥위치로 나가는법을 했는데 1,2번 최적의 탈옥위치가 아닌 아예 다른곳이 오히려 최적의 값이 될 수 있음
3. 1번이 특정지점으로 탈옥하려면 4, 2번이 특정지점으로 탈옥하려면 3 이라고 하면 총 7만 듬
지금 1,2번 둘 다 최소값이 아닌데 합쳐보니까 이게 최소의 문을 연 방법이였음!

따라서, 탈옥위치들을 모두 한번씩 
아니 근데 이게 문을 열면 계속 열려있으니까 공유가 되야되잖아

for point1 
for point2
bfs(죄수1, point1) 
bfs(죄수2, point2)

for point1
for point2
bfs(죄수2, point2)
bfs(죄수1, point1)







면 탐색으로 불가한 영역이라고 치면 그리디나 dp로 접근을 해보고 싶은데
어떻게 나가야 문을 적게 나갈 수 있을까라는 걸 그리디로 1도 생각이 안나고