그래프 썸네일형 리스트형 SCPC 2017 본선 4번 풀이. 방 바꾸기 문제 설명www.codeground.org 참조 풀이, Part 1 (부분문제 2)원래 그래프를 G라고 하자. G에서 임의의 간선은 최대 하나의 사이클에만 속하므로, 사이클을 이루는 정점들을 하나로 묶은 그래프 T를 생각하자. 사이클을 이루지 않는 정점은 그대로 홀로 둔다. T는 트리가 된다. 왜냐면, T의 정점들이 사이클을 이룬다면 애초에 하나로 묶였을 것이기 때문이다. * 원래 그래프의 정점과 구분하기 위해 T의 정점과 간선은 슈퍼정점과 슈퍼간선으로 표현할 것이다.* INF = 무한대 (Infinity)의 약자로 쓸 것이다. T의 슈퍼정점들 중, 빈 방의 처음 위치를 포함하는 슈퍼정점이 딱 하나 있을 것이다. 이 슈퍼정점을 트리 T의 루트 R(T)로 하자. 빈 방은 R(T)의 자식슈퍼정점 중 일부를 .. 더보기 이전 1 다음