mintuchel   1년 전

제가 너무 어렵게 생각한 것일 수 도 있는데 최근 트리의 지름 관련 문제를 풀어서인지 아래와 같은 방법으로 접근했습니다.

1. 어느 지점이든 잡아서 해당 지점으로부터 가장 먼 지점을 구한다.

2. 구해진 먼 지점을 기준으로 다익스트라를 수행한다.

→ 다익스트라로 나온 dist 배열중 가장 큰 값을 구한다

→ 해당 값이 해당 땅에서 가장 먼 두 지점 사이의 거리이다.

하지만 아래와 같은 map이 통하지 않더라구요

3 2
LL
LL
LW

이런 map이 나오면 만약 맨 왼쪽 위 지점으로 가장 먼 지점을 고르는 첫번째 과정을 진행했을떄

오른쪽 중앙의 L이 나오게 되어 오답이 뜨더라구요.

혹시 제 방법으로는 아예 못푸는 것인가요?

BFS로 브루트포스 돌려서 풀긴했는데... 제가 생각한 방법으로는 아예 안되는건지 궁금하네요

저 위와 같은 반례를 해결할 수 있을까요??

너무 궁금합니다.

도와주시면 감사하겠습니다!

oh040411   1년 전

네, 트리가 아닌 일반적인 그래프의 지름(가장 먼 두 정점)을 구하는 알려진 방법은 모든 정점 쌍의 최단 경로를 구하는 방법 (BFS n번, 다익스트라 n번, 플로이드 워셜 등)밖에 없습니다.

https://en.wikipedia.org/wiki/...

mintuchel   1년 전

오 소스 감사합니다!!

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