핵심

: destPos까지의 최단경로가 아니다. destPos까지 가는데의 최소 거울의 수를 구하는 것이다.

왜 틀렸을까? : 첫번째 전략

: 방문처리에 대해 생각해보자.

• 내 전략
  : 타겟에 dir 와 cnt 를 가지고 방향이 변경되면 ,
  큐에다가 dir 변경되고, cnt 를 증가하는 방식으로 진행함...
  -> 큐에다가 뺑뺑이 돌리면서 진행한다.
  : w와 h가 100이기 때문에 10000 의 영역에서 뺑뺑이 돈다.

-> 맞게 했는데도 테케 통과하지만, 3퍼센트에서 틀린다.

• 하기전에 메모리에 대해서도 생각해보자.
  

왜 메모리 초과일까?

• destPos 까지의 최단경로가 아니라, 거울을 최소한 사용하기 위한
  탐색을 진행한느 것이다.
  나는 visited 배열을 이용해서 계속 거울 최소값을 찾기 위해서

최대 100*100 의 공간 안에서 이와 같은 조건으로 큐에 집어넣으면서 처리하고 있다. 그리고 솔직히 visited 불처리가 아니기 때문에
큐 넣는 비율이 굉장히 커질 수 있다.

• C 의 오른쪽 화살표에서 먼저 진입하는 경우, visited 처리되면서 아래에서는 진입 못하는데, 우리는 최단 경로가 아니라,
  최소로 거울 사용하는 것이므로,
  visited 재방문 해야 한다.

• 상상의 나래를 피자.
  : 예를 들면 지금까지 우리는 visited 을 이용해서 한번 방문하면 못 들어가! 인데, 지금의 경우에는 어 조금이라도 작네???
  그럼 들어와이기 때문에 메모리 초과할 수 있따.

결론

• 최단경로 구할때 사용한 visited 변수인데, 어떠한 정보를 토대로 해서 재방문이 가능하게 해야 한다.
  -> 잘못 건드리면 메모리 초과발생한다.
  : 기존에 했던 bfs로 하면 안됨을 의미하기 때문에
  해결 전략을 다시 생각해보는 것도 좋은 방법이다.

  

  ---

  틀을 깨야 한다.

• 문제를 보고 bfs다! 해서 진행하는 것이 아니라,
  -> 문제에 맞는 방법의 코드를 작성하려고 노력하자.
  

• 일단 확실히 알 수 있는 거는 거울이 없다면 타겟 pos에 대해서
  모든 직선거리는 동일한 값을 가진다.

  정답

• 1) 한줄을 그냥 싹다 그어버리자.

• 2) 그러면서 중간에 벽이 있다고 하면 정지!

• 전부 1로
  

• 전부 2로
  

• 전부 3으로
  

• 전부 4로