인프런 커뮤니티 질문&답변
작성한 질문수
4-C 질문있습니다 :)
작성
·
162
0
안녕하세요 선생님 🙂
문제를 풀다가 정신이 나가버릴거 같은 느낌은 이 문제풀면서 처음 겪는거 같습니다.. 어떻게든 풀려고 하루종일 박치기를 해봐도 어질어질하네요..ㅠㅠ
인접행렬을 만들어주는거는 예전에 배웠던 적이 있기 때문에 무리없이 이해했습니다.
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배열이 어떤 아이디어로 생성된 배열인지 모르겠습니다..
그동안 문제들을 풀면서 몇 번의 벽이 느껴졌었지만 항상 시간을 박으면서 극복해왔습니다. 근데 이 문제는 도저히 해결이 안될거 같은 벽처럼 느껴지네요.. 선생님의 도움이 절실히 필요합니다 흑흑..
답변 1
0
안녕하세요 유태님 ㅎㅎ
}
for(int i = 1; i < (1 << n) - 1; i++){이부분이죠?
이 문제는 2개의 컴포넌트로 나눠야 하는 문제입니다. 즉, 이 2개의 컴포넌트로 나눌 수 있는 경우의 수가 아닌 것은 배제행야죠? 그부분이 바로 0000, 1111 따위입니다. 그래서 해당부분은 포함하지 않아야 합니다.
근데 이 comp배열이 어떤 아이디어로 생성된 배열인지 모르겠습니다..
>> connected component라고 생각하시면 됩니다. 이부분은 2주차에 배웁니다.
코드를 해석하자면 다음과 같습니다.
comp[11]: 각 정점이 어느 구역에 속하는지를 저장하는 배열 (0 또는 1).
이렇게 할 경우에 access violation이 뜨는데요, 도대체 뭘까요?? ㅠㅠ
>> 제 컴파일러에는 뜨지 않습니다 혹시 스샷 가능할까요?
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
안녕하세요 유태님 ㅎㅎ
왜 저런 에러가 뜨는지 알겠습니다.
저게 1111이 되게 되면
int idx1 = -1, idx2 = -1;이 코드에서 idx2나 idx1은 -1로 초기화가 된 상태로 유지가 됩니다.
이 때 dfs() 호출하게 되고 여기서
pair<int, int> dfs(int idx, int value)
{
visited[idx] = 1;idx에 -1이 들어가게 되니 생기는 에러인 것 같습니다.
감사합니다.
아.. 1111이게 된다면 구역이 2개가 아닌 1개밖에 있을 수 없기 때문에 성립할 수 없는거였군요!! 감사합니다 선생님 🙂 문제는 다시 한번 차근차근 풀어보겠습니다 :)
http://boj.kr/0b919b15a71149228ec75a196c6dc02a
이 코드구요, 선생님 코드와의 차이점은 for (int i = 1; i < (1 << N) - 1; i++)를 for (int i = 1; i <= (1 << N) - 1; i++)로 변경한 것밖에 없습니다.
아래의 부분에서 access violation에러가 뜹니다