dhtjstlr777   3년 전

목적지에 방문이 가능한 경로에 포함되는 노드를 poss 라는 2차원 벡터에 true로 정의하고

그렇지 않거나 아직 알 수 없는 노드를 false로 정의했습니다.

따라서 DFS 탐색 중 목적지에 도달하게 되면 경로에 해당하는 노드는 true로 변경하여

해당 경로에 포함되는 노드를 방문할 시 더 이상 방문하지 않도록 하였습니다.

시간초과가 아닌 틀렸습니다가 나와 반례를 찾고 있습니다. ㅠㅠ

saberia404   3년 전

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년 전

N = 4 라고 할 떄,

1 2 2 3

1 1 3 3

3 1 1 3

3 2 1 0

우선 위 코드에서 답 4 제대로 나오는 것 같습니다.

첫번째 실행하였을 때 표시된 1이 먼저 poss가 되더라도 이미 해당 노드에서 탐색할 수 있는 모든 노드는 스택에 들어있으므로 문제가 없는 것 같습니다.

houma757   3년 전

4

1 2 2 3

1 1 3 3

3 1 1 3

3 2 1 0

정답 : 5

출력 : 4

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