인프런 커뮤니티 질문&답변
작성한 질문수
14502번 재질문 드립니다
작성
·
193
0
http://boj.kr/840f45d321eb47839eab789e324f7551
안녕하세요 저번에 답변 받은 후에도 잘 이해가 안가서 다시 질문드립니다!
================================================
안녕하세요. ㅎㅎ
벽을 세우고 >> 해당 경우의 수에 따른 로직
이후에... 또 다시 벽을 세우잖아요?
즉, A라는 테스트를 진행하고 다시 B라는 테스트를 진행하기 때문에 B라는 테스트에 A에서 방문한 정점이 반영되면 안되요ㅎㅎ
각 테스트마다 visited 를 초기화하는 부분이 필요한 것같습니다.
그리고 다음에 코드 올리실 때 백준코드 >> 공유버튼을 눌러서 링크로 남겨주세요.
이렇게 올리시면 제가 보기가 넘 힘들어요 ㅠ
감사합니다.
강사 큰돌 올림.
==================================
이렇게 답변 주셨었는데, 32번째 라인부터 36번째까지 초기 배열로 초기화를 하기 때문에 각 테스트마다 이전 테스트의 결과가
반영안되는 것 아닌가 궁금해서 질문드립니다
12일간 계속 맞왜틀 시전중이라 꼭 답변 부탁드립니다. 감사합니다!
답변 1
0
ㅎㅎ 언제든지 물어보세요. ㅎㅎ
음..
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
visited[i][j] = arr[i][j];
}
}
for (int i = 0; i < 3; i++) {
visited[s[i].first][s[i].second] = 1;
}
일단 이부분은 초기화는 맞는데요.
이 문제에서 필요한 로직은
벽을 세우고 >>> 탐색 입니다.
즉, 벽을 세우는 것도 여러개의 경우의 수가 필요하고 해당 경우의 수마다 ... "탐색"을 해야 하니 탐색을 초기화를 시켜야 하는 것이죠. 일단 탐색에 관해 초기화하는 것은 이해 하신 것같습니다.
그러나 지금 이 부분이 이해가 안된다는 말씀 같은데..
for (int i = k; i < h.size(); i++) {
s.push_back(h[i]);
combi(k + 1);
s.pop_back();
}
아니 분명 초기화 시켰는데 왜 또 이런식으로 pop_back()을 하냐... 그런 말씀이시죠?
자 그래서 제가 그림을 그려봤습니다.
일단 visited를 초기화 하는 것은 좀 분리해서 생각해주세요.
먼저 벽을 세운다만 집중해보죠.
저렇게 pop_back()을 하는 것은 이렇게 2개를 벽을 세웠죠? 그 다음에 오른쪽에 세우는 경우의 수를 체크하고... 그리고 다시 pop_back()을 한다음 오른쪽이 아닌 아래쪽에 벽을 세우는 경우의 수를 체크해야 하니까 그런 겁니다.
이건 초기화라고 보기엔 좀 그렇고.. 벽을 세우고.. 다시 벽을 치웠다가 또 다른 벽을 세운다. 라고 보시면 됩니다.
이렇게 벽을 세우고 >> 초기화 >> 탐색 이렇게 일어난다고 보시면 됩니다.
탐색에 대해 첨언하자면 이렇게 벽을 세우는 경우의 수마다... "탐색"이 많이 일어나니. 탐색할 때마다 visited 초기화는 당연히 해야 되는 것이구요.
감사합니다.