시간이제법지났으니

관심있는사람들은다

생각해봤으리라믿고


저는이렇게풀어봤읍니다

저는아재니까종이에직접


그래프를그리고

색칠을해보면서


어떻게할까생각을정리해봤읍니다.


1. 색깔의순서


아래A를보면4번노드에?가있져

왜냐면더이상칠할색이없어서요

이그래프는분명색칠되는건데요


빨파녹순으로무작정색을써버리면

얼마못가서곤란에처하게되더군요


그전노드들을다른색깔로바꾸고다시하면

B그림처럼제대로색칠을할수있게됩니다


처음부터3번을녹색이아닌빨강을사용했다면

뒤로돌아가서다시해볼필요없이바로됐겠죠


3번에서빨강과녹색이쓰일수있었는데녹색을

아무생각없이칠했더니4번에서사단이난거죠


각노드별로색깔을고를때

사용할수있는색깔들중에

빨파녹순으로우선순위를


적용하는게이런상황을방지할수있는방법인것같더라고요

각노드별로빨파녹우선순으로색칠해본것이B그림입니다



2.노드방문순서


D그래프를보면1번부터순차적으로탐색했을때

제일마지막에가서이그래프는안된다는걸알죠


반면,C그래프는한4번째정도에파악이되더라고요

4365순서로진행해봤읍니다#1에서처럼각노드에


빨파녹순으로칠하면서요처리순서의기준은연결된

이웃의수입니다연결이많은놈부터적은놈순으로요


이렇게하니까위에서처럼문제가생겼을때뒤로돌아가서색깔을바꿔도안된다는걸금새알수있었읍니다

한노드의색깔을정하려면이웃들색깔을먼저파악해야되니까요이웃이많을수록해당노드에서사용할수

있는색이줄어들게되겠죠그럼뒤돌아가서색깔을바꿔도어차피경우의수는똑같을수밖에없게되는거죠


따라서이런식으로하면문제가발생했을때

빨리포기할수있게되죠구지다른색깔들로

다시해보지않아도말이죠


아래그림도이런차이점을좀더확실히보여주고있읍니다



다시정리해보면,


1.색깔은항상빨파녹순으로우선순위를두고골라라

2.연결된이웃이많은노드부터우선적으로처리해라


이두가지를염두해두고코드를짜봤읍니다