invrtd_h   3년 전

그래프 이론에서 path는 보통 각 정점과 간선을 최대 한 번까지 지나가는 경로를 말하지만, 이 문제에서의 path는 오히려 그래프 이론의 walk와 같은 용어로 정의되는 것처럼 보입니다. 그리고 실제로 그렇게 가정하고 푼 풀이가 통과합니다.

https://en.wikipedia.org/wiki/Path_(graph_theory)

풀이에 대한 블로그 : https://seastar105.tistory.com...

hjroh0315   3년 전

상관이 없을 것입니다.

짝수 번 지나간 경로는 자동적으로 XOR에 의해 값에 영향을 주지 않게 되므로, simple path나 그냥 path나 해석상에서 큰 차이가 없게 됩니다.

hjroh0315   3년 전

또한, path라는 단어를 walk라는 의미로 사용하는 사례도 심심찮게 보이는 편이며, 이 경우는 언급하신 의미를 전달하기 위해서 (simple graph의 개념을 빌려서) "simple path" 라는 표현을 사용합니다.

invrtd_h   3년 전

@hjroh0315 상관 있습니다. 반례 첨부합니다. 짝수 번 지나간 간선이 단절선이 되어서 경로를 끊어 버리는 반례입니다.

path라는 단어를 walk로 사용하는 사례가 존재하는군요... 아무튼 저는 이 문제를 풀 때 그런 뜻으로 해석하지 못해서 혼란스러웠었습니다.

preview

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