목록2009~2014/C/C++ (225)

되는대로 살자

[C언어 기출문제&풀이] 두 색으로 칠하기(Bicoloring)

평면 위에 지도가 있을 때, 각 영역을 인접한 다른 영역과 구분할 수 있게 서로 다른 색으로 칠하고자 한다면, 네가지 색만 있으면 된다는 4색 정리(four-color theorem)라는 것이 있다. 이 정리는 100년이 넘게 증명되지 않은 채로 남아 있다가 1976년에 컴퓨터의 도움을 받아서 증명될 수 있었다. 여기에서는 조금 더 쉬운 문제를 풀면 된다. 어떤 그래프가 주어졌을 대 그 그래프를 두 색으로 칠할 수 있는지, 즉 모든 정점을 빨간색 또는 검은색으로 칠할 때 인접한 정점이 같은 색으로 칠해지지 않게 할 수 있는지 알아보자. 문제를 간단하게 하기 위해 그래프가 연결 그래프고, 무방향 그래프며, 자체 루프가 없다고(즉(x,x)같이 한 정점에서 출발해서 그 정점을 ㅗ바로 연결되는 모서리가 없다고)..
2009~2014/C/C++ 2011. 5. 16. 01:21
이전 Prev 1 ··· 29 30 31 32 33 34 35 ··· 225 Next 다음