1261번 - 알고스팟
아직 다익스트라를 어떻게 쓰는지 잘 모르는데, bfs에 추가적인 요소를 더해주니 AC되어서 공유합니다.
메모리가 101824 KB로 아슬아슬하게 통과했네요... 좋은 풀이는 아닌 듯 하니 참고만 해주세요!
https://www.acmicpc.net/proble...
2206 벽 부수고 이동하기 풀이랑 거의 똑같이 작성했습니다.
방문 체크하는 visited 배열을 3차원 배열로 만들고, 마지막 요소는 벽 뚫은 횟수로 지정했습니다.
bfs 함수 안 28번째 줄에서, 다음 칸이 1이면 벽 부순 횟수(limit)를 1증가시킵니다.
29번째 줄에서, 다음 칸(newy, newx)에서 이미 같은 limit으로 방문한 적이 있는지 체크합니다.
이때 newlimit < 200 조건도 같이 넣어주지 않으면 시간초과가 납니다.
상한선이 200인 이유는, n, m 의 최댓값이 각각 100이므로 시작과 끝을 제외한 모든 칸이 1이라고 가정했을 경우
벽 부순 횟수는 200칸을 넘을 수 없기 때문입니다.
정점사이의 거리가 모두 같은 그래프이므로
최단경로를 bfs로 구할 수 있고
다익스트라보다 시간복잡도도 낮아 bfs 풀이가 정해라고 판단됩니다.
댓글을 작성하려면 로그인해야 합니다.
123kbg 4년 전 1
아직 다익스트라를 어떻게 쓰는지 잘 모르는데, bfs에 추가적인 요소를 더해주니 AC되어서 공유합니다.
메모리가 101824 KB로 아슬아슬하게 통과했네요... 좋은 풀이는 아닌 듯 하니 참고만 해주세요!
https://www.acmicpc.net/proble...
2206 벽 부수고 이동하기 풀이랑 거의 똑같이 작성했습니다.
방문 체크하는 visited 배열을 3차원 배열로 만들고, 마지막 요소는 벽 뚫은 횟수로 지정했습니다.
bfs 함수 안 28번째 줄에서, 다음 칸이 1이면 벽 부순 횟수(limit)를 1증가시킵니다.
29번째 줄에서, 다음 칸(newy, newx)에서 이미 같은 limit으로 방문한 적이 있는지 체크합니다.
이때 newlimit < 200 조건도 같이 넣어주지 않으면 시간초과가 납니다.
상한선이 200인 이유는, n, m 의 최댓값이 각각 100이므로 시작과 끝을 제외한 모든 칸이 1이라고 가정했을 경우
벽 부순 횟수는 200칸을 넘을 수 없기 때문입니다.