ntopia   7년 전

대피소에 반드시 구호물자를 보내야 한다고 생각하는 민지는 현재 위치인 1번 교차로에서 대피소가 있는 N번 교차로까지 어떤 도로를 선택하며 가더라도 지나친 교차로를 다시 방문하지 않는다는 것을 증명해 트럭 운전사들을 설득하려 한다.

이 부분을 저는 이렇게 해석했습니다.

"1번부터 N번까지 이동하는 경로 중에 도중에 사이클을 포함하고 있는 것이 있는지/없는지"


1번에서 시작하여 N번까지 가는 길에는 사이클이 없어도 다른 길에 사이클이 존재할 수 있는데,

이 경우는 NO CYCLE 을 출력해야 한다고 해석했고, 그렇게 푼 4070971번 소스는 틀렸습니다.


그래서 N번 교차로 까지 가는 길에는 사이클이 없어도 다른 길에 사이클이 존재할 때

CYCLE 을 출력하게 한 4071036번 소스는 맞았습니다.


출력부분의 설명을 보면 저처럼 해석하는 쪽이 맞는 것 같습니다.

1번 교차로에서 N번 교차로까지 가는 과정 중 지나쳤던 교차로를 다시 방문하는 경우가 생길 수 있으면 CYCLE, 그렇지 않다면 NO CYCLE을 출력한다.

이 것이 의도한 바가 맞는지요?


예를 들면 다음과 같은 데이터에서는 NO CYCLE을 출력함이 맞아보입니다.

ntopia   7년 전

혹시 저만 이렇게 해석한 것이라면

괜히 태클 걸어서 죄송합니다........

ii200400   2년 전

5년전 댓글이지만 다른 분들도 저처럼 글을 읽고 있을 것 같아 댓글을 남깁니다.

저의 경우 "운행을 거부한 트럭운전사들 때문에 난관에 봉착했다. 강력한 폭풍의 영향으로 내비게이션은 정확하지 않고, 도로를 구분할 수 있는 표지판이 망가졌기 때문에 트럭운전사들은 교차로에서 어떤 도로를 선택해야 할지 모른다." 라는 지문 때문에 정말 길을 모른다는 가정이 있으므로 (n정점으로 가는 길을 모름)

어떻게든 사이클이 생기면 무조건 CYCLE을 출력하도록 만들었고 패스를 받았습니다. 윗글의 예제도 CYCLE로 출력하는 것이 맞습니다.

```

4
2
2 3
1
4
1
1

CYCLE

```

현실이었다면.. 막다른 길목인지도 확인했겠지만요 하하..

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