wondy1128   7년 전

문제를 보고 2가지 cost로 (1,2) 작성하면 된다고 처음에 생각했었는데 

예시를 보고 안된다는 것을 확인하고 질문검색으로 4색정리를 이용해라 라는 것을 보았습니다. 

그런데 3색을 사용하는 경우만 생기는 것이지 않나 싶은 생각밖에 안들어서 질문작성합니다.


저의 생각이 

부모-자식 이 있는 경우에는 1-2 , 2-1 로 칠하는 경우

부모의부모 - 부모 - 자식 이있는 경우엔 (1,2,3) 으로 

1-2-3 / 1-2-1

1-3-2 / 1-3-1

2-1-3 / 2-1-2

2-3-1 / 

3-1-2 /

3-2-1 / 

총 6가지 로 생각이 되는데 자식이 한개가 존재할 때 여러개가 존재할 때로 나누어 보았습니다. 

그리고 위 경우의 수가 계속 반복해서 일어날 경우의 가장 최소를 구해야한다. 라는 것으로 문제를 생각하였는데

이런 방식은 틀린 접근인지.. 질문 올립니다...!


문제 분류가 DP, 트리 인 것은 확인 했는데 

BFS로 풀어보려했습니다. 아래는 틀렸지만 작성한 코드입니다...

댓글을 작성하려면 로그인해야 합니다.