nahwasa   4년 전

로직은 우선 2차원 배열로 해보니, 벽을 부순애가 먼저 해당 지점에 도착해서 길을 막는 경우가 생겨서 3차원 배열로

벽을 부순 횟수에 따라 서로 다른 방문 체크 배열을 사용하도록 했습니다.

문제는 시간초과를 어디서 잡아야할지 감이 잘 안옵니다.

1000x1000x10짜리라 쉽게봤더니 생각보다 시간이 오래걸리네요 ㅠ

일단 시간 줄이기위해 생각해본것은

  1. 벽 부순 횟수가 현재 들어가려는 좌표지점보다 작으면 들어감 -> 근데 최소 벽부순 횟수로 구하는게 아니고 시간으로만 보니 이건 아닐것같고요..
  2. 가려는 곳이 현재보다 시간을 많이쓴곳이면 들어감 -> 역시 그럼 이 경우 빨리 가더라도 차후에 벽을 못부수는 경우가 생길 것 같아요.

힌트 부탁드립니다!

djm03178   4년 전

arr의 원소의 의미가, 벽이 있으면 true, 없으면 false인가요? 그렇다면 단순히 이를 false로 변경하는 것으로 방문 체크를 할 수 없어 보입니다. false로 되어있어도, 벽이라고 판단하고 같은 곳을 여러 번 방문할 수 있겠네요.

nahwasa   4년 전

일단은 벽이 없으면 true 입니다. (갈 수 있다는 의미로)

아..?

그렇네요. false로 갈 수 없다고 체크해도 지나온 지점을 벽이라 판단하고  부수고 뒤로 갈수가 있겠군요 ㅋㅋ

감사합니다! 다시해보겠습니다.

nahwasa   4년 전

@djm03178

덕분에 성공했습니다 ㅠ 사랑해요. boolean대신 int배열로 3종류로 체크하니 되는군요!


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