(8/1) 7일차 - 그래프 알고리즘 기초 문제

어제와 같이 문제를 풀었습니다. 총 13문제였습니다.

https://bas.ioikorea.cc/problems/list

2022 여름학교 처음반

 

1. 인접 리스트     O

말그대로 vector를 이용하는 인접리스트를 구현해주고 각각을 오름차순으로 정렬하여 출력해주면 되는 기초문제입니다.

 

2. 너비 우선 탐색     O

queue를 이용하여 그래프에서의 너비 우선 탐색을 진행하면서 이전까지 방문하지 않은 정점을 방문하게 된다면 queue에 push해주는 동시에 값을 출력해주면 너비 우선 탐색의 정점 방문 순서와 동일한 순서로 값들이 출력됩니다.

 

3. 깊이 우선 탐색    O

너비 우선 탐색과 같은 방식으로 출력해주면 됩니다. queue대신 vector를 순회하며 재귀함수로 구현해주면 됩니다.

 

4. 가장 짧은 사이클   X

DFS로 풀었더니 알수없는 이유로 TLE가 발생했습니다. 더 빠르게 해주려면 BFS를 이용하여 cycle이 발생하는 순간 cycle의 길이를 출력해주고 bfs를 종료해주면 됩니다. 이 과정을 1 ~ N까지 반복하여 최소의 cycle 길이를 출력해줍니다.

아직 해결하지 못함. 작성중

 

5. 국밥    O

결론적으로는 방향 그래프에서의 다익스트라 문제입니다. 시작하는 마을 S를 기점으로 priority_queue에 간선들의 가중치를 넣고 방문하지 않은 정점과 잇는 가중치라면 선택해주고 해당 정점에서 다른 마을을 잇는 간선들을 추가해주는 작업을 반복합니다. 모든 정점을 방문하였다면(priority_queue가 empty라면) 반복을 종료하고 각 정점까지 잇는데 필요한 가중치의 값들을 순서대로 출력해줍니다.

 

6. 두 번째 최단 경로    X

한번의 다익스트라에 경로 저장 배열을 2개 만들어서 해결이 가능하다고 합니다.

아직 해결하지 못함. 작성중

 

7. 최소 신장 트리    O

기초적인 Minimum Spanning Tree 구현 문제입니다. 크루스칼로 가중치 합을 구해주었으며 판별을 위해 Union-Find를 사용하였습니다. priority_queue에 맨 앞에 있는 간선이 연결하는 두 정점의 부모가 같다면 무시하고 같지 않다면 Union으로 두 부모를 같게 만들어줌과 동시에 답에 해당 간선의 가중치를 더해주는 작업을 반복합니다.

 

8. 단절점    O

단절점의 중요한 특징 2가지를 안다면 풀 수 있습니다.

     1. 단절점을 기준으로 그래프가 분리된다. 즉, DFS Spanning Tree로 탐색하였을 때 단절점보다 이후에 탐색된 정점들은 이전에 탐색된 정점들과 이어지는 것이 불가능하다(분리된다) 

     2. 만약 루트 정점이라면 자식이 2개 이상일 때 단절점이다

이 사실을 바탕으로 DFS Spanning Tree를 만들고 두 가지 조건 중 하나 이상을 만족하는 지를 확인해주면 됩니다.

 

9. 단절선    X

단절점을 응용하면 됩니다. 구현은 비슷

아직 해결하지 못함. 작성중

 

10. 오늘 뭐 먹지?     X

아직 해결하지 못함. 작성중

 

11. 그래프 그리기 문제    X

아직 해결하지 못함. 작성중

 

12. 탑 쌓기    X

아직 해결하지 못함. 작성중

 

13. 사진    O

a가 b보다 작다라는 것을 vector[a].push_back(b) 형태의 인접 그래프로 표현해주었습니다. 이후 priority_queue에 indegree 가 0인 노드들을 넣고 하나씩 빼면서 만약 outdegree가 존재한다면 해당 outdegree들로 이동해 indegree를 1씩 빼주면서 indegree가 0이 된 정점들을 추가적으로 priority_queue에 넣어주는 방식으로 순서를 구할 수 있습니다.