Graph Theory(2)
-
BOJ 13361 : 최고인 대장장이 토르비욘
https://www.acmicpc.net/problem/13361 13361번: 최고인 대장장이 토르비욘 전성기 시절의 오버워치는 지구 상에서 가장 진보된 최첨단 무기를 보유했으며, 그 무기의 출처는 바로 토르비욘 린드홀름이라는 전무후무한 기술자의 작업장이었다. 하지만 이런 토르비욘에 www.acmicpc.net 여학 때 못 풀어서 1달 동안 힌트 + 생각해보고 푼 문제이다. 유니온 파인드로 서로 길이가 같은 것끼리 묶어주고, 이중 전체 변 길이의 합에서 서로 다른 (그룹에 있는 것들의 갯수)개의 길이를 빼면 된다. 풀이 자체는 아주 간다하지만, 정말이지 사람이 이걸 어캐 생각할 수 있는지 모르겠다. 코드
2021.11.15 -
BOJ 22344 : 그래프 균형 맞추기
https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 개인적으로 이번 KOI 고등 1번 난이도>>>>>>>이번 KOI 고등 2번 난이도라고 생각한다. 먼저 모든 정점의 가중치를 x+a나 -x+b로 표현 가능하다. 이를 통해 가중치의 합의 최소 = 절댓값 함수에서의 최솟값을 이용하면 된다. 이때 사이클이 있을때의 예외를 잘 처리해야 하는데, 사이클이 있을 때 어떤 임의의 두 인접한 정점에서 유일한 x값이 나오는 경우가 있다. 이를 주의하..
2021.08.01