juseung0619   1년 전

백트래킹 로직에서 Group 객체가 cy, cs, groups 리스트를 함께 상태로 관리하며 재귀적으로 조합을 탐색하고 있습니다. 이때, 재귀가 끝난 뒤 상태를 복구하는 과정에서 아래 두 가지 방식 중 '복구 로직 1'만 정답이 되고, '복구 로직 2'는 오답이 발생하는 이유가 궁금합니다.

// 복구 로직 - 1 (정답)
int last = group.groups.remove(group.groups.size() - 1);
if (map[hm.get(last).y][hm.get(last).x] == 'Y') group.cy--;
else group.cs--;

// 복구 로직 - 2 (오답)
if (map[hm.get(group.groups.size() - 1).y][hm.get(group.groups.size() - 1).x] == 'Y') group.cy--;
else group.cs--;
group.groups.remove(group.groups.size() - 1);


왜 remove 전에 참조하는 방식(group.groups.size() - 1)이 문제가 되는지?

재귀 내부에서 Group 객체가 공유되기 때문에 참조 시점과 제거 시점 사이에 groups 리스트가 변경되지 않는다면, 같은 값이 나와야 하지 않나요?

doju   1년 전

2번 로직은 group.groups.size()-1번 칸을 참조하고 있는데, 의도하신 건 group.groups.get(group.groups.size()-1)번 칸일 것 같습니다.

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