둘 다 틀리는 게 맞는 것 같은데, 운이 좋았거나 데이터가 약한 것 같습니다.
vector<int>의 경우 아마 초기화를 따로 하지 않으면 자동으로 0이 됩니다. 그런데 w[i]는 i번 축사에 배정된 소의 번호이므로 w의 크기는 N+1이 아니라 M+1이 되어야 합니다.
초기값을 0으로 생각하는 경우 0이라는 값이 메모리상에서 우연히 걸릴 확률이 높기 때문에 통과가 된 것으로 보이고, -1로 한 경우 배열을 조금만 벗어나도 잘 나오지 않는 값이기 때문에 이미 배정된 소가 있는 것으로 생각한 것으로 보입니다.
imno1234 5년 전
축사 배정 문제를 풀던 중 아래와 같은 케이스를 접하게 되었습니다.
(전형적인 이분매칭 알고리즘을 사용했습니다.)
아래의 코드는 WA를 받은 코드인데, 이 코드의 11,19번째 줄을 주석에 있는 코드로 바꾸면, 즉 vector의 초기화 값은 -1에서 0으로만 바꾸고, 조건문만 같이 수정해주면 AC가 뜹니다...
왜 이런일이 생긴건지 궁금합니다. 감사합니다.