mgtkiwi_48   1년 전

위쪽의 코드가 정답 코드, 아래쪽은 틀린 코드입니다. 

위쪽은 한 단지의 카운트(this_cnt)를 vector에 넣으면서 정렬 후 출력했고

아래쪽은 단지 개수(total_cnt)를 단지의 번호로 보고, 해당 단지의 bfs에 들어가면 cntArr[total_cnt] 해당하는 단지의 카운트를 센 후,
최종적으로는 vector에 다시 넣어 정렬 후 출력하는 방식입니다. 

0개의 단지나 1개의 단지, 1개로 이루어진 단지 등은 맞았는데.. 어떤 반례에서 틀렸던 걸까요?

굳이 아래쪽처럼 할 필요가 없긴 하지만.. 그냥 궁금해서 질문해봅니다..

playsworld16   1년 전

답을 담는 배열인 cntArr의 크기가 작습니다.

0과 1이 체스판처럼 번갈아가면서 나타나는 입력을 생각해보면, 그 때 총 단지 수는 약 N*N/2정도가 됩니다. 

N이 10일때 벌써 10*10/2 = 50이 됩니다.

N=25일 때 25*25/2 = 약 320 정도로 배열의 크기를 키우면 맞을 겁니다.

참고로, C++의 정적 배열에서 범위 밖의 인덱스로 접근하는 것은 UB(Undefined Behavior), 즉 어떻게 동작할지 예상할 수 없게 됩니다.

mgtkiwi_48   1년 전

아.. 너무 기본적인 실수였네요. 친절한 설명 감사드립니다!

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