rkdgh98   3달 전

코드에 대해 설명드리자면

  1. 어떤 한 경로 a가 도착지점에 도달하면 도달하기 위해 거쳐왔던 경로의 path값을 각각 1씩 더해줍니다.
  2. 만약 다른 경로 b가 위 경로 a와 부딪혔을 때, 탐색을 중단하고 돌아가면서 b의 path에 부딪힌 칸의 path 값만큼 더해줍니다.
  3. 결국 path[1][1]에는 모든 path값이 더해질 것이고, 이것이 답이됩니다.

아래는 문제의 TC를 통해 만들어진 path 값들입니다.

 
 3 2 2 2 1
 1 0 0 1 1
 1 0 0 1 0
 1 1 1 1 0


이렇게 생각하고 풀었는데, 더이상 어떤 방법으로 시간을 줄일 수 있는 지 모르겠습니다.

도와주시면 감사드리겠습니다 !!

djm03178   3달 전

어떤 지점 (a,b)에서 끝으로 가는 길이 단 하나도 없었다고 가정해봅시다. 이 경우 path[a][b]의 최종 값은 얼마가 될까요?

또, 이 지에 대한 탐색을 이미 끝낸 후, 나중에 다른 경로를 통해 다시 이 지점을 오게 되면 어떻게 될까요?

rkdgh98   3달 전

@djm03178 

소중한 시간 내셔서 답변 달아주심에 정말 감사드립니다!!

죄송하지만.. 말씀 이해가 잘 되지 않네요 ㅠㅠ

끝으로 가야지만 그때부터 if(a==m&&b==n) { return 1; }를 통해 path에 1이 더해지기 때문에, 끝으로 갈 수 있는 길이 아예 없다면 path[1][1]은 초기값 0으로 유지되지 않나요?

탐색을 끝낸 뒤에 나중에 다른 경로를 통해 다시 이 지점을 오게 되면, if(path[a][b]>0) { return path[a][b]; }를 통해 그 지점에 저장되어 있는 path 값을 가지고 되돌아 가도록 짠건데, 제가 제 코드를 잘못 이해하고 있는걸까요?

djm03178   3달 전

path[1][1]만 0인 게 아니라 path[a][b]도 0이 될 거고, 그러면 이미 path[a][b]가 계산이 끝난 상태인데도, 나중에 다시 (a,b)에 갔을 때 0이 바로 반환되는 게 아니라 다시 탐색을 들어간다는 것을 말씀드린 겁니다.

rkdgh98   3달 전

아!!!!!!!!!!!!!!!!!!!!!!!

그래서 시간이 더 걸리는거였군요 

정말 감사드립니다 ㅠㅠ

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