반례입니다.

답은 4가 나와야 하는데 7이 나옵니다.

63번째줄과 70번째 줄에서

다음 칸에 해당 방향으로 이미 방문한 적이 있고, 다음 칸의 거울의 최소 횟수가 지금의 횟수보다 작은 경우 방문을 하지 않는데

반례에서 12행 9열의 교차하는 부분의 '.'에서를 보면

위에서 내려올 때의 거울 최소값인 1로 먼저 그 칸의 CNT값이 갱신되고 나서,

4행 2열을 통해서 도달하는 루트 1가지, 

4행 7열을 통해서 도달하는 루트 1가지로 12행 9열에 도달하게 되는데

이 때 둘 중 나중에 12행 9열에 도달하는 루트는

1)해당 방향으로 12행 9열에 이미 도달한 적이 있고

2) 해당 칸의 CNT값이 현재의 거울 최소횟수보다 낮으므로

12행 9열에 방문하지 않게 되고, 해당 경로를 체크하지 않게 됩니다.

반례에서는 4행 2열을 통해서 도달하는 루트가 최단인데, 이 루트가 큐에서 나중에 pop되어

체크가 안되는 듯 합니다.

감사드립니다 해결해보겠습니다!!

해결했습니다.. 반례 너무 칼같이 잘 잡아주셨네요 ㅠㅠ.. 감사합니다.

일단 원인을 보자면 처음에

continue; 조건을 두가지로 나누었습니다. 1) 해당 방향 방문  2) 그 위치까지 도달하는데 걸린 최소 거울 수

문제는 세 가지 경로에서 비교할 수 있습니다.

거울을 설치할 수 없는 위치인 '.'에서 최적 경로가 지나가기 전에 최적이 아닌 두 가지 경로가 위의 두 가지 조건을 모두 최적인 것처럼 1) 따로 2) 따로 갱신해버리고 지나가버렸습니다.

1. 최적 경로
2. 방향은 같지만 거울 수가 더 많은 경로
3. 방향은 다르지만 거울 수가 가장 (1, 2 보다)적은 경로

2, 3번 경로가 먼저 교차점을 지나가 버려서 조건 1), 2)를 갱신해버린 것이 문제였습니다.

제 코드에서 해결 방법은

나누어진 두 개의 방문배열(방향, 거울 수)이 2, 3처럼 완전히 독립되어버리는 case가 존재한다는 것이었기 때문에 이 두 가지를 하나로 합치는 것이 해결책이었습니다.

결국 방향 별로 visited값을 갱신하고 방향 별로 같거나 작은 값만 지나갈 수 있도록하여 방향이 다르다면 더 큰 visited값이라도 '.'를 지나갈 수 있도록 했습니다.

같은 방향이라면 더 적은 거울 수가 100% 최적일 것이고, 다른 방향일 때는 더 적은 거울 수가 더 먼 길을 돌아 최적이 아닐 수 있기 때문입니다.

좋은 지적 감사드립니다.