p.262 전보문제

[ZeroOnePro]

안녕하세요
전보문제에서 x에서 y로 메시지를 보낼 때, x에서 y로 가는 경로와 y에서 x로 가는 경로가 모두 존재해야만 메시지를 전송할 수 있다고 써있는데, 소스코드에서

for d in distance:
   if d != INF
      count +=1
     max_distance = max(max_distance, d)

해당 부분에서 d를 보면 x에서 y로 가는 최단경로는 INF가 아니라면 존재하지만, y에서 x로 간다는 보장을 할 수 있을까요?

x     M     y   

| -> | -> |
   
|      | <- |      

요런 형태가 만약 주어져도 문제가 없을지 궁금합니다

감사합니다

[ndb796]

안녕하세요.

질문하신 내용 확인했습니다 :)

아마 경로와 통로의 의미를 헷갈리셔서 오해하신 것 같습니다.

일단 그래프 이론에서 경로(Path)란 같은 간선을 두 번 이상 포함하지 않는 길을 의미합니다. 즉, 일반적으로 경로라는 함은 A에서 B로 이동하기 위한 여러 개의 간선으로 구성된 길을 지칭합니다.

본 문제에서 통로는 하나의 간선(Edge)의 의미로 사용되었습니다. 또한 문제에서는 X에서 Y로 메시지를 보낼 때, X에서 Y로 가는 통로가 있어야 메시지를 보낼 수 있다고 명시되어 있습니다. 이는 X에서 Y로 연결된 간선이 있어야 메시지를 보낼 수 있다는 의미와 동일합니다. 다시 말해 방향 그래프의 의미를 내포하고 있으며, 말씀하신 문장인 '양방향 경로가 있어야 메시지를 전송할 수 있다'는 내용은 명시되어 있지 않습니다.

혹시 제가 질문을 잘못 이해한 부분이 있다면, 다시 코멘트 남겨주세요.

감사합니다.
나동빈 드림