[일반] n분 그래프의 최솟값 문제 백준에 있음?

[익명(1.236)]

https://www.acmicpc.net/problem/9932

Baekjoon Online Judge

이거랑 똑같은 문제를 풀고 싶은데 이건 문제(데이터 만들기 7)를 위한 문제라서 풀 수가 없음.

구글링하거나 첨부된 파일 보면 풀이는 금방 나오는데 그래도 자력으로 풀어보고 싶어서 풀이는 안 볼거임

이분 그래프가 가능하냐 안 하냐는 1707번에 있긴 함

평면 그래프 중 4분 그래프는 언제나 가능하고 이건 아마 16746번인 거 같음

[익명(59.6)]

np-complete아님?? 풀이 어디서 봄

[익명(1.236)]

그냥 구글에 그래프 색칠, 컬러링 이렇게 치면 나오던데? 풀이도 그냥 완전탐색마냥 풀걸.

[익명(1.236)]

풀이는 일부러 대충 봤는데 아마 완전탐색마냥 풀걸. 코드만 보기를 원하면 데이터 만들기 7, 데이터 만들기8의 코드를 보셈.

[익명(59.6)]

올라와있는 코드를 터뜨리는 문제잖아 시간안에 도는 코드가 아닌데

[익명(1.236)]

그렇긴 한데 느린 알고리즘도 알고리즘 아님? 스도쿠 푸는 문제도 n 작을 때, 클 때 문제 따로 있잖아

[익명(106.102)]

16746은 간선 기울기가 0, inf, +-1이라는 조건이 있음. 너가 말한 문제는 k-colorability로 일반적인 그래프에서는 np complete임. 이 글이랑 큰 관련은 없지만 27511는 cycle 모양의 그래프를 3-coloring하는 문제야.