longlive   3년 전

이 문제에서 색깔을 칠할 때 start를 1로 하고 이어져 있지 않아서 안된 부분에 대해서는 visit 둬서 색깔을 다 칠하게 한 뒤 탐색하면 해결되기는 하지만,..

색깔을 칠할 때 시작 기준점을 모든 vertex에 대해서 다 해보고 탐색 안해봐도 되는 이유가 있을까요,??

ex)시작 기준점을 vertex 1로 했을 때와 시작 기준점을 vertex 2로 했을 때의 색깔이 칠해지는 모습(?)이 다를 수 있는데 그런 경우는 탐색을 안해봐도 되는 이유

질문 이해하신 분.,, 답변 부탁드립니다.

djm03178   3년 전

이분 그래프인 경우 색이 칠해지는 모습은 단 하나밖에 될 수 없습니다. 정확히는 각 연결된 컴포넌트에 대해서 특정 정점을 어떤 색으로 하느냐에 따라 나머지가 자동으로 결정이 됩니다.

longlive   3년 전

감사합니다!

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