알고리즘 스터디

• 백준 9372 상근이의 여행 O
• 백준 1991 트리 순회 O
• 백준 15805 트리 나라 관광 가이드 O
• 백준 11725 트리의 부모 찾기 O
• 백준 19542 전단지 돌리기 ~

알고리즘 스터디

백준 9372 상근이의 여행

• https://www.acmicpc.net/problem/9372

• 비행 스케줄은 항상 연결 그래프를 이룬다
  이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다
  -> 연결 그래프의 모든 노드를 순회하기 위해 필요한 간선의 최소 개수를 구하는 문제

• 풀이:
  DFS / BFS를 이용하여 그래프를 순회하며 모든 노드를 방문하기 위해 사용되는 간선의 수를 센다

• 더 간단한 풀이:
  n개의 정점을 가진 연결 그래프에서 최소 연결 부분 그래프의 간선의 개수는 (n-1)개

백준 1991 트리 순회

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-1991-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C

백준 11725 트리의 부모 찾기

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-11725-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EB%B6%80%EB%AA%A8-%EC%B0%BE%EA%B8%B0

⚡백준 19542 전단지 돌리기

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-19542-%EC%A0%84%EB%8B%A8%EC%A7%80-%EB%8F%8C%EB%A6%AC%EA%B8%B0

📌참고자료

• 최소 신장 트리(MST, Minimum Spanning Tree)
  https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

• 신장 트리 (Spanning Tree)

1. 그래프의 신장 트리 = 그래프의 최소 연결 부분 그래프
2. 그래프에서 (n-1)개의 간선을 선택해서 만든, 그래프 내의 모든 정점을 포함하는 트리

• 신장 트리의 특징

1. 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다
2. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다
3. DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다
   -> 탐색 도중에 사용된 간선만 모으면 만들 수 있다

• 최소 신장 트리 (MST, Minimum Spanning Tree)

1. 최소 신장 트리 = 사용된 간선들의 가중치 합이 최소인 신장트리
2. 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다
   -> MST를 구현하는 방법으론 Kruskal 알고리즘, Prim 알고리즘 등이 있다