coronal95   2년 전

중복된 위치의 좌표를 계속 지나쳐서 메모리 초과가 뜨는 것 같기도 한데.. 어떻게 고쳐야 할 지 감이 잡히지 않습니다. 도와주시면 감사하겠습니다.

jh05013   2년 전

BFS의 중복 체크를 다시 공부해 보세요.

coronal95   2년 전

bool형 visited배열을 하나 더 선언한 후에 지나친 곳을 check해 주면 많은 반례가 생기더군요.. 그래서 중복된 좌표를 다시 돌더라도, (n-1,m-1)에 맨 처음 도착할 때의 dist값을 return해주면 된다고 생각했습니다. 

뭔가 다른 방법을 찾아야 할 것 같은데, int dist[1000][1000][2];로 각 좌표까지 가는데 걸리는 시간을 메모이제이션해서 구하는 방법 말고 다른 방법을 찾아보고 싶습니다.. 혹시 다른 idea가 있으시다면 조언 감사드리겠습니다.

jh05013   2년 전

[1000][1000][2]가 바로 풀이입니다. 좌표라고 해서 특별한 게 아니고 그냥 상태의 일부이기 때문에, 벽을 부쉈는지 여부를 저장해도 어색한(?) 점은 없습니다.

저도 다른 방법은 딱히 안 떠오르고, 있더라도 적어도 이 풀이보다는 어렵거나 느릴 것 같습니다.

djm03178   2년 전

dist에 메모이제이션까지도 필요 없습니다. bool visited[1000][1000][2];면 충분합니다. 거리는 BFS를 하면서 자연스럽게 나오는 거기 때문에 이걸 메모이제이션할 필요가 없습니다.

coronal95   2년 전

감사합니다ㅠㅠ 제가아직 미숙한 것 같습니다.. 덕분에 많이 배웠습니다!

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