그래프 간선이
1 2
1 3
2 4
3 5
이렇게 되어있으면
첫번쨰 bfs 들어가서 1번 노드가 1로 칠해지고 (paint = 1)
2 3 번 노드가 -1 로 칠해지고 큐에 들어갈텐데 (paint = 0)
이제 큐 맨 앞에가 2고 paint 는 1
4는 1로 칠해지고 큐에 추가
그 다음은 맨 앞이 3 이고 paint 는 0
5는 0으로 칠해지고 큐에 추가
그런데 4 랑 5가 같은 너비라서 색깔이 같아야 되는데 아님..
요약하자면
너비당 정점이 하나가 아닌데,
paint = !paint; // 너비 증가할 때마다 색 반전
이 줄 떄문에
큐에서 하나 뺄 때마다 색 반전, (너비 증가할 떄가 아님)
minjea917 3년 전
처음에 정점을 칠하는 paint 변수를 선언한 뒤, 너비가 변할 때 paint 변수 값을 반전하는 식으로 짰더니
12%에서 계속 틀려 29라인을 30 라인처럼 바꾸니 바로 정답이 됐습니다만..
29, 30 라인 둘의 차이를 모르겠습니다.
어차피 둘 다 너비가 변하면, 색 반전 (1과 0)이 일어나고,
첫 정점이 0으로 시작하든 1로 시작하든지도 상관 없지 않나요?
제가 잘못생각하고 있는 건가요?