https://www.acmicpc.net/problem/2026
Solution
ref: https://westmino.tistory.com/84
I thought of traversing the friendship graph with DFS or BFS. It’s not actually a graph, but the friendship relationships given as input can be used to implement something like DFS/BFS on a graph.
- adj_mat: Adjacency matrix storing friendship relationships.
- adj_list: An array where the i-th element contains i’s friends.
DFS
The definition of “friends” here is that everyone must be mutual friends with each other. Friends of friends don’t count.
- Set an arbitrary point as the starting point
- path: array storing people who can go together
- Get people who are friends with the starting point from adj_list.
- Use adj_mat to check if step-2 people can be added to path.
- If path length reaches K, return path
- If path length doesn’t reach K after all exploration, return None
DFS Result Handling
DFS yields either None or a path.
- None: Set a different person as the DFS starting point and re-run DFS
- path: Sort the path and return it
Code
https://github.com/naem1023/codingTest/blob/master/graph/acmicpc-2026.py