4 - E 경사로 문제

Question

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 4 - E 경사로 문제를 영상 보기 전에 구현해봤는데 어디가 틀린 부분인지 도저히 모르겠습니다. 행과 열을 나눠 각 칸마다 다음 칸과 비교하는 방식으로 문제를 풀어봤는데.. 게시판이나 여러 반례 케이스들을 대입해봐도 틀린 부분이 어딘지 모르겠습니다... 살려주세요 ㅠ http://boj.kr/5559f53ca9f24925ac272571115de33d

큰돌 · Answer

안녕하세요 태현님 ㅎㅎ 2가지부분이 잘못됬습니다. 이부분 고치시면 통과합니다 . checkBuildDownHeight 부분의 기본적인 return true가 없습니다. check.. 함수부분의 배열 out of index에 대한 처리가 없습니다. 제가 한번 다듬어 봤는데요. 참고 부탁드립니다. #include #include #include using namespace std; vector adj[105]; bool visited[105][105]; int n, l; int answer; // 현재 칸 기준 앞으로 탐색 (가로) bool checkBuildDown(int y, int x) { if (x + l > n) return false; int height = adj[y][x]; for (int i = 0; i < l; i++) { // 높이가 다르다면 false 리턴 if (adj[y][x + i] != height) return false; // 높이가 같은 경우 건물을 지었다고 체크 visited[y][x + i] = true; } return true; } // 세로 bool checkBuildDownHeight(int y, int x) { if (y + l > n) return false; int height = adj[y][x]; for (int i = 0; i < l; i++) { if (adj[y + i][x] != height) return false; visited[y + i][x] = true; } return true; } // 현재 칸 기준 뒤로 다시 탐색 (가로) bool checkBuildUp(int y, int x) { if (x - l + 1 < 0) return false; int height = adj[y][x]; for (int i = 0; i < l; i++) { // 높이가 다르다면 flase 리턴 if (adj[y][x - i] != height) return false; // 이미 설치된 경사로가 있으면 false 리턴 if (visited[y][x - i]) return false; } return true; } // 세로 bool checkBuildUpHeight(int y, int x) { if (y - l + 1 < 0) return false; int height = adj[y][x]; for (int i = 0; i < l; i++) { // 높이가 다르다면 flase 리턴 if (adj[y - i][x] != height) return false; // 이미 설치된 경사로가 있으면 false 리턴 if (visited[y - i][x]) return false; } return true; } void checkWidth(int y) { bool ret = true; for (int x = 0; x < n; x++) { // 다음칸이 존재하지 않는 경우 break; if (x + 1 == n) break; // 이미 ret이 false인 경우 break; if (ret == false) break; // 해당 칸과 다음 칸이 같은 경우 if (adj[y][x] == adj[y][x + 1]) { continue; } // 해당 칸보다 다음 칸이 적은 경우 else if (adj[y][x] > adj[y][x + 1]) { // 차이가 1 이상이면 ret = false if (adj[y][x] - adj[y][x + 1] > 1) ret = false; // 해당 칸보다 뒤쪽에 경사로 설치가 불가능하다면 ret = false, 종료 if (x + l > n - 1) { ret = false; break; } // 경사로 설치가 불가능하다면? ret = false if (!checkBuildDown(y, x + 1)) ret = false; } // 해당 칸보다 다음 칸이 높은 경우 else if (adj[y][x] < adj[y][x + 1]) { // 차이가 1 이상이면 ret = false if (adj[y][x + 1] - adj[y][x] > 1) ret = false; // 해당 칸보다 앞쪽에 경사로 설치가 불가능하다면 ret = false, 종료 if (x - (l - 1) < 0) { ret = false; break; } // 경사로 설치가 불가능하다면? ret = false if (!checkBuildUp(y, x)) ret = false; } } // ret가 true인 경우에만 answer 1 증가 if (ret) { answer++; } } void checkHeight(int x) { bool ret = true; for (int y = 0; y < n; y++) { // 다음칸이 존재하지 않는 경우 break; if (y + 1 == n) break; // 이미 ret이 false인 경우 break; if (ret == false) break; // 해당 칸과 다음 칸이 같은 경우 if (adj[y][x] == adj[y + 1][x]) { continue; } // 해당 칸보다 다음 칸이 적은 경우 else if (adj[y][x] > adj[y + 1][x]) { // 차이가 1 이상이면 ret = false if (adj[y][x] - adj[y + 1][x] > 1) ret = false; // 해당 칸보다 뒤쪽에 경사로 설치가 불가능하다면 ret = false, 종료 if (y + l > n - 1) { ret = false; break; } // 경사로 설치가 불가능하다면? ret = false if (!checkBuildDownHeight(y + 1, x)) ret = false; } // 해당 칸보다 다음 칸이 높은 경우 else if (adj[y][x] < adj[y + 1][x]) { // 차이가 1 이상이면 ret = false if (adj[y + 1][x] - adj[y][x] > 1) ret = false; // 해당 칸보다 앞쪽에 경사로 설치가 불가능하다면 ret = false, 종료 if (y - (l - 1) < 0) { ret = false; break; } // 경사로 설치가 불가능하다면? ret = false if (!checkBuildUpHeight(y, x)) ret = false; } } // ret가 true인 경우에만 answer 1 증가 if (ret) { answer++; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> l; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int temp; cin >> temp; adj[i].push_back(temp); } } for (int i = 0; i < n; i++) { memset(visited, false, sizeof(visited)); checkWidth(i); memset(visited, false, sizeof(visited)); checkHeight(i); } cout << answer; } 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.