2589번 - 보물섬
제가 너무 어렵게 생각한 것일 수 도 있는데 최근 트리의 지름 관련 문제를 풀어서인지 아래와 같은 방법으로 접근했습니다.
1. 어느 지점이든 잡아서 해당 지점으로부터 가장 먼 지점을 구한다.
2. 구해진 먼 지점을 기준으로 다익스트라를 수행한다.
→ 다익스트라로 나온 dist 배열중 가장 큰 값을 구한다
→ 해당 값이 해당 땅에서 가장 먼 두 지점 사이의 거리이다.
하지만 아래와 같은 map이 통하지 않더라구요
3 2LLLLLW
이런 map이 나오면 만약 맨 왼쪽 위 지점으로 가장 먼 지점을 고르는 첫번째 과정을 진행했을떄
오른쪽 중앙의 L이 나오게 되어 오답이 뜨더라구요.
혹시 제 방법으로는 아예 못푸는 것인가요?
BFS로 브루트포스 돌려서 풀긴했는데... 제가 생각한 방법으로는 아예 안되는건지 궁금하네요
저 위와 같은 반례를 해결할 수 있을까요??
너무 궁금합니다.
도와주시면 감사하겠습니다!
네, 트리가 아닌 일반적인 그래프의 지름(가장 먼 두 정점)을 구하는 알려진 방법은 모든 정점 쌍의 최단 경로를 구하는 방법 (BFS n번, 다익스트라 n번, 플로이드 워셜 등)밖에 없습니다.
https://en.wikipedia.org/wiki/...
오 소스 감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
mintuchel 1년 전
제가 너무 어렵게 생각한 것일 수 도 있는데 최근 트리의 지름 관련 문제를 풀어서인지 아래와 같은 방법으로 접근했습니다.
1. 어느 지점이든 잡아서 해당 지점으로부터 가장 먼 지점을 구한다.
2. 구해진 먼 지점을 기준으로 다익스트라를 수행한다.
→ 다익스트라로 나온 dist 배열중 가장 큰 값을 구한다
→ 해당 값이 해당 땅에서 가장 먼 두 지점 사이의 거리이다.
하지만 아래와 같은 map이 통하지 않더라구요
3 2
LL
LL
LW
이런 map이 나오면 만약 맨 왼쪽 위 지점으로 가장 먼 지점을 고르는 첫번째 과정을 진행했을떄
오른쪽 중앙의 L이 나오게 되어 오답이 뜨더라구요.
혹시 제 방법으로는 아예 못푸는 것인가요?
BFS로 브루트포스 돌려서 풀긴했는데... 제가 생각한 방법으로는 아예 안되는건지 궁금하네요
저 위와 같은 반례를 해결할 수 있을까요??
너무 궁금합니다.
도와주시면 감사하겠습니다!