https://www.acmicpc.net/problem/24782
24782번: Coloring Graphs
To address the impending STEM shortage early on, your local elementary school decided to teach graph theory to its kindergarten students! To tap into their age-specific skills, the students are asked to color the vertices of a graph with colors of their
www.acmicpc.net
영어로 되있는 문제긴한데..
간단하게 그래프의 정보를 입력하면, 그 그래프에서 이웃하는 정점들간에 색이 겹치지 않도록 모든 정점을 색칠하는 최소 색의 개수를 구하는 문제이다.
문제에 있는 이미지인데, 보면 이해가 잘된다.
일단 기본 접근은 가장 많은 정점과 연결된 정점부터 탐색을 시작하는 것이었다.
근데, 그렇게 해도 최적해가 안나오는 경우가 있어서, 그냥 모든 정점부터 탐색하게 설정했더니 클리어됬다.
한 정점에서만 탐색해서 결과값이 나오게 하려고 이짓 저짓 다해봤는데 결국 이걸로 클리어라니.. 뭔가 좀 허탈했다.
클리어 당시의 코드인데
일단 모든 정점에서 탐색하므로 정렬 부분이 필요없고,
가장 적은 컬러 사용 수를 넘어가면 바로 return 시켜버리게 하면 속도에 영향이 있을 것같다.
원래 해볼 생각은 없었는데, 글 적다보니 얼마나 변할지 궁금해서 시도해봤다.
별로 차이가 없어서 실망했다.
'자기개발 > BOJ' 카테고리의 다른 글
| [BOJ 3830] 교수님은 기다리지 않는다. (0) | 2023.02.05 |
|---|---|
| [BOJ 3779] 주기 (0) | 2022.12.24 |
| [BOJ 11967] 불켜기 (0) | 2022.12.23 |
| [Solved Gold IV] 결! 합! (0) | 2022.11.18 |
| [Solved Gold V] 제곱 수 찾기 (0) | 2022.11.11 |