N = 4 라고 할 떄,
1 2 2 3
1 1 3 3
3 1 1 3
3 2 1 0
이라는 입력 케이스가 있다면, 표시된 1로 가는 방법은 2가지이다. 그런데, 표시된 1에서 목적지로 가는 방법도 2가지이다. 그러므로 정답은 4가 되어야 한다.
하지만 위 코드에서는 첫번째 실행하였을 때 표시된 1이 먼저 poss 벡터에 체크되어, 정답이 3이 나온다.
- 참고
1, 2번째 경로:
1 2 2 3
1 1 3 3
3 1 1 3
3 2 1 0
3번째 경로:
1 2 2 3
1 1 3 3
3 1 1 3
3 2 1 0
dhtjstlr777 3년 전
목적지에 방문이 가능한 경로에 포함되는 노드를 poss 라는 2차원 벡터에 true로 정의하고
그렇지 않거나 아직 알 수 없는 노드를 false로 정의했습니다.
따라서 DFS 탐색 중 목적지에 도달하게 되면 경로에 해당하는 노드는 true로 변경하여
해당 경로에 포함되는 노드를 방문할 시 더 이상 방문하지 않도록 하였습니다.
시간초과가 아닌 틀렸습니다가 나와 반례를 찾고 있습니다. ㅠㅠ