[250905] Day 26 - 죽이고싶은 BFS 문제와의 10선

들어가며

오늘 BFS 문제와의 단판승부가 있었다. 그리고 내가 졌다.

분하다… 내가 이길 거라고 생각했는데, 까고보니 내가 질 수 밖에 없더라… ㅋㅋㅋ 그래도 약간 알고리즘 재활치료 한다고 생각하고 열심히 다시 노력해봐야겠다.

오늘의 키워드

트리의 지름 구하기

오늘 문제를 풀면서 만났던 상황은 이거였다.

바둑판처럼 격자로 연결되어있는 그래프가 주어지는데, 가장 먼 두 점 사이의 거리를 구하라.

 

그래서 문제를 해결하기 위해서 고민을 좀 많이 했는데, 나름 내가 방법을 고안해냈다.

1. 그래프의 아무 점이나 방문하면서 시작함.
2. BFS로 해당 점부터 그래프의 모든 점까지의 거리를 측정한다.
3. 거기에서 가장 먼 거리를 가진 점들이 가장 먼 거리를 구성하는 노드의 후보로 선택된다. (한쪽 끝 지점이 될 수 있는 후보)
4. 각 후보에 대해서 BFS를 수행하여, 각 후보 노드로부터 가장 먼 노드 거리들을 찾는다.
5. 후보의 먼 거리 중 가장 긴 노드 거리를 선택한다.

처음에는 한 번에 가장 멀리 떨어진 두 노드를 선택하려고 했었는데, 이게 쉽지만은 않은 일 같았다. 좋은 위치를 선택한다고 하더라도 고려해야 할 게 좀 많은 느낌쓰.

 

그래서 아예 한 점을 잡고, 거기에서 가장 먼 점을 선택하는 방법을 하려고 했는데, 내가 선택할 수 있는 점이 여러 개가 나오는 문제가 또 발생했다. 그래서 그 다음에는 아예 이것들을 후보로 지정해서,

이런 식으로 진행을 하면 처음에 그래프 상에서 어떤 점을 선택하더라도 가장 먼 점들을 찾을 수 있을 것이라 생각했다.

 

그러나, 문제 자체가 그냥 격자로 이어져있기 때문에 “트리 형태”가 아니라 사이클이 존재하는 그래프이고, 이로 인해 위 알고리즘이 적용되지 않는다는 문제가 있었다. 트리 구조인 경우에 A→B 의 경로가 유일하게 하나 존재하기 때문에 괜찮지만, 사이클이 있는 경우에는 같은 거리라도 여러 경로가 존재할 수 있어 고려할 게 더 많아지는 것으로 생각된다.

 

비록 문제 해결에는 실패했지만, 트리 구조에서 가장 먼 두 점 사이의 거리를 구하는 방법을 하나 배웠다. 이건 이제 절대로 까먹지 않을 것 같은 내용.

 

심지어 내가 풀려고 했던 문제는 그냥 모든 노드에서 무작정 BFS를 돌리고 보는 브루트포스 문제였다는거… 근데 그게 정답인가봄;;;

 

https://blogshine.tistory.com/111

[알고리즘] 트리의 지름 : Diameter of Tree