0 1 1 1 1
0 0 1 0 0
1 0 1 0 0
1 1 1 1 1
0 0 0 0 0
요런 맵 (0이 벽, 1이 길)있을때
최장경로 찾는 제일 구현이 쉬운 방법은 모든 시작점에 대해 BFS 돌리는건데
이거말고
연결가능한 덩어리 중의 한 점을 시작점으로 bfs돌린다음 그 점에서 구할수 있는 가장 먼 점이
이 덩어리에서 구할 수 있는 최장경로의 양 끝점 중 하나다. <- 요런 알고리즘 있지않음?
예전에 수업때 배운것같은데 이거 쓰면 틀리길래 내 기억이 틀렸거나 뭔가 잘못사용하고있나 궁금함
위에 올린 맵 기준으로 하면
그냥 모든 맵 스캔하다가 (0,1)에서 BFS 스타트, (2,0)이 현재 점에서 제일 먼 점이라는걸 찾음,
(2,0)이 이 덩어리에서 최장경로의 양 끝점 중 하나란걸 알았으니까 거길 시작점으로 다시 BFS 돌림
그럼 (0,4)가 거리 8 떨어져 있다는 걸 알고 정답은 (2,0)->(0,4)인 길이 8 짜리 경로
이런 알고리즘 없나?
내 기억이 구라까는건지 아니면 다른 알고리즘인데 내가 잘못쓰는건지 알려줘
그거 트리에서 dfs로 지름구하는방법 아님?
트리지름
그른가? 내가 말한 문제유형에선 못쓰지? 반례좀 알려줘.. 보물섬 같은 문제 이렇게 풀었다가 틀렸는데 반례를 모르겠어 저것도 늘어트리면 트리로 볼수있지않나?
사이클이 존재할수도 있어서 트리로는 못 볼듯 - dc App
저거 트리로 만들려면 biconnected component 별로 묶어야될거같음 근데 묶어도 컴포넌트 내에서 또 길이 구해야되서 힘들거같은데 - dc App
이건 왜 안 되지?가 아니라 왜 트리일 때는 되는거지? 로 생각을 해야함.
아 맞네 사이클이 bfs돌리면서 끊어져서 각각 붙은채로 체크되니까 변조되겠네 고맙!!!!!!
반례를 얘기하자면, 트리에서는 되니까 반례는 사이클을 포함해야겠지? 1-2-3-4-5-6-7-8-1이 싸이클을 이루는 상태에서 1에 9, 5에 10이 연결된 상태에서 3에서 제일 멀리 있는 점은 3-4-5-6-7을 타는 7이지만 최장거리는 9-1-2-3-4-5-10이 됨.