4-C 질문있습니다 :)

Question

안녕하세요 선생님 🙂 문제를 풀다가 정신이 나가버릴거 같은 느낌은 이 문제풀면서 처음 겪는거 같습니다.. 어떻게든 풀려고 하루종일 박치기를 해봐도 어질어질하네요..ㅠㅠ 인접행렬을 만들어주는거는 예전에 배웠던 적이 있기 때문에 무리없이 이해했습니다. for(int i = 1; i < (1 << n) - 1; i++) 모든 켜져있는 경우를 체크하려면 for(int i = 1; i <= (1 << n) - 1; i++)이 되어야하지 않나요? n이 6일 경우에, 111111을 빼고 111110까지만 체크하는 이유를 모르겠습니다. 이렇게 할 경우에 access violation이 뜨는데요, 도대체 뭘까요?? ㅠㅠ 비트가 켜져있는 모든 경우를 체크하여 켜져있을 경우에 comp배열에 1을 저장하고, 그 값이 dfs함수에서 두번째 파라미터와 같다면 재귀를 돌리고, 재귀를 돌린 값으로 누적을 시키신건 알겠습니다. 근데 이 comp배열이 어떤 아이디어로 생성된 배열인지 모르겠습니다.. 그동안 문제들을 풀면서 몇 번의 벽이 느껴졌었지만 항상 시간을 박으면서 극복해왔습니다. 근데 이 문제는 도저히 해결이 안될거 같은 벽처럼 느껴지네요.. 선생님의 도움이 절실히 필요합니다 흑흑..

큰돌 · Answer

안녕하세요 유태님 ㅎㅎ } for(int i = 1; i < (1 << n) - 1; i++){ 이부분이죠? 이 문제는 2개의 컴포넌트로 나눠야 하는 문제입니다. 즉, 이 2개의 컴포넌트로 나눌 수 있는 경우의 수가 아닌 것은 배제행야죠? 그부분이 바로 0000, 1111 따위입니다. 그래서 해당부분은 포함하지 않아야 합니다. 근데 이 comp배열이 어떤 아이디어로 생성된 배열인지 모르겠습니다.. >> connected component라고 생각하시면 됩니다. 이부분은 2주차에 배웁니다. 코드를 해석하자면 다음과 같습니다. comp[11]: 각 정점이 어느 구역에 속하는지를 저장하는 배열 (0 또는 1). 이렇게 할 경우에 access violation이 뜨는데요, 도대체 뭘까요?? ㅠㅠ >> 제 컴파일러에는 뜨지 않습니다 혹시 스샷 가능할까요? 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.