123kbg   4년 전

아직 다익스트라를 어떻게 쓰는지 잘 모르는데, 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칸을 넘을 수 없기 때문입니다.

yukariko   4년 전

정점사이의 거리가 모두 같은 그래프이므로

최단경로를 bfs로 구할 수 있고

다익스트라보다 시간복잡도도 낮아 bfs 풀이가 정해라고 판단됩니다.

댓글을 작성하려면 로그인해야 합니다.