18,38번줄빼고 visited 는 코드에 영향을안줍니다.
16933번 - 벽 부수고 이동하기 3
코드를 정확히 읽지 않았습니다. visited에 벽을 부순 횟수를 저장하는 것은 의미가 없는 것 같습니다. 맵 안에서 어떠한 경로로 왔느냐에 따라서 crashed의 값이 달라질 수 있으며 crashed가 visited[nx][ny]의 값보다 작다고 해서 무조건 정답인 것이 아니므로 코드의 로직이 틀린 것으로 보입니다.
그러나 1. 가장 빨리 어떠한 벽에 도착한 경우가 이후로부터 방문될 crashed의 값의 최솟값이라면 그것이 정답이거나 이 벽을 지나치지 않은 경로가 정답일 확률이 높으므로 문제가 없고 2. 가장 빨리 어떠한 벽에 도착한 경로가 답이 되지 않는다면 정답이 꼭 그 벽을 부숴야 한다면 정답은 가장 빨리 도착했을 때의 crashed 값보다 작을 것이 분명하므로 통과되었을 것으로 보입니다.
1.에 해당하는 예제로 K가 3일 때 (4,4), (7,7), (7,8)에 가장 빨리 도착한 값이 이후로부터 방문될 crashed보다 작으면 그 경로가 정답이 될 확률이 높습니다. 예를 들어 4,4는 (3,3) -> (3,4) -> (4,4) 를 통해 방문할 수 있으나 이것이 최단경로가 아니므로 (4,4)을 (4,2) -> (4,3)을 통해 이동하는 것이 crashed의 값이 가장 작으면서 최단 경로입니다.
2.에 해당하는 예제로 K가 5일 때 만일 (8,9)에 가장 빨리 도착한 경로가 답이 되지 않는다면 가장 빨리 도착했을 떄의 crashed의 값은 최대가 될 수 없습니다. 빨간색은 벽에 해당하며 가장 빠른 경로는 (8,9) -> (10, 9) -> (11,9)...을 차례대로 부시는 것이므로 (4,9)와 (8,9)을 부신 경로는 최단 경로가 될 수 없습니다.
제가 틀렸을 수도 있습니다. 또한 말 또는 내용이 이해가 안될 때 질문하는 것은 환영합니다.
아마 +1을 안하는게 좋은거같음
내 현재 crashed = 3이라하고
벽을 부순곳을 3, 혹은 4로 바꿨을때로 가정해봅시다
3으로 바꾼 경우:
3 -> 4으로 가는 경우부터 들어갈 수 없음 (2~3이 마지막)
4로 바꾼 경우:
4 -> 5로 가는 경우부터 들어갈 수 없음 (3~4가 마지막)
근데 3 -> 4로가는 가장 빠른 길은 맨 처음 crashed = 3에서 도착했을때였음
나중에 이 벽에 도착하는 3 crashed는 굳이 일로 갈 필요가 없음. 오히려 성능손해임
즉. +1을 하면 굳이 갈 필요가 없는데 벽을 한번 더 박치기한거임
이경우, 최적은 찾을수 있을텐데
쓸데없는 경우의 수가 더 que에 들어가서
시간손해가 생길거임
근데 왜 되는가? 왜 시간손해가 없는가?
+1을 했다 치고 벽을 꺠고 난 이후를 생각해보죠
처음 깨고 간놈의 crashed는 4인데
이러면 벽주위의 빈공간은 4, 벽은 5가될거임
즉 처음 깨고 간놈이 벽주위의 빈공간을 전부 4로 바꿔놓고가서
나중에 깬놈이 4의 crashed로 갈 수 있는 공간은 벽밖에 없음
즉 주변에 벽이 많았으면 que에 쓸데없는게 더 많이들어가고
벽이 없었으면 쓸데없는게 별로 안들어간다는거임
근데 벽을 부술수 있는 갯수 제한이 10개밖에안돼서
그래서 아마 된걸로 판단됨
다들 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
marigold2003 1년 전
55번 줄에서, visited에 벽 부순 횟수를 저장할 때 벽을 부쉈으니까 +1을 해서 저장해야 한다고 생각했습니다.
그런데 실행 결과, 저 +1이 있어도 정답이고 없어도 정답이더라고요.
왜 없어도 정상 작동하는지 궁금합니다.