문제를 잘못이해한게 죄수가 탈옥을 하기 위한 최소의 경로를 찾는게 아니라 문을 최대한 적게 열고 나가야하는점이다.
즉 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도 생각이 안나고
'Algorithm > Algorithm Problem' 카테고리의 다른 글
백준 14722 우유도시(DP) (0) | 2022.10.24 |
---|---|
백준 2931 가스관(구현, 시뮬레이션) (0) | 2022.10.24 |
백준 2631 줄세우기(LIS, DP) (1) | 2022.10.18 |
땅지원의 A형 대비 기출 분석 (0) | 2022.10.13 |
SWEA 2117 홈 방문 서비스(BFS) (0) | 2022.10.12 |