minjea917   3년 전

처음에 정점을 칠하는 paint 변수를 선언한 뒤, 너비가 변할 때 paint 변수 값을 반전하는 식으로 짰더니

12%에서 계속 틀려 29라인을 30 라인처럼 바꾸니 바로 정답이 됐습니다만..

29, 30 라인 둘의 차이를 모르겠습니다.

어차피 둘 다 너비가 변하면, 색 반전 (1과 0)이 일어나고,

첫 정점이 0으로 시작하든 1로 시작하든지도 상관 없지 않나요?

제가 잘못생각하고 있는 건가요?

n99joon   2년 전

그래프 간선이 

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   2년 전

오래전에 질문한 건데 지나치지 않고 답변해주셔서 정말 감사합니다!

며칠 고민하다가 그냥 놓아준 문제인데 이렇게 해결되니 정말 기쁘네요

n99joon   2년 전

제 질문은 같은 질문이 4년쨰 답변이 안되고잇어요 ㅋㅋ 

도와드릴수 잇어 다행입니다

수고하십시오!

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