BFS 당근마켓 승원이 문제 질문이 있습니다!

Question

안녕하세요! 큰돌님. 문제를 풀다가 자꾸 visited 배열에 오버플로우가 일어나는 것 같아서 예시 코드와 비교해 봤더니, 큰돌님은 max_n = 104로 배열의 크기를 최대로 정의 해 놓으셨더라구요. 그래서 큰돌님 처럼 다음과 같이 배열의 크기를 최대로 해놓고 하니, 문제가 해결되었습니다. const int max_n = 104; 저는 입력받는 코드를 따로 만들지 않아서, 크기를 예측할 수 있는 코드여서 5X5 로 정의를 해놓았는데, 왜 오버플로우가 일어나는 지 궁금합니다! 제가 작성했던 코드 첨부하겠습니다. // Online C++ compiler to run C++ program online #include using namespace std; const int max_n = 104; int dy[4] = {-1, 0, 1, 0}; int dx[4] = {0, 1, 0, -1}; int main() { int N = 5; int M = 5; int x,y; int visited[N][M] = {0,}; //방문 노드 //시작 지점 int sx = 0, sy = 0; //끝 지점 int ex = 0, ey = 4; //MAP int map[N][M] = { {1,0,1,0,1}, {1,1,1,0,1}, {0,0,1,1,1}, {0,0,1,1,1}, {0,0,1,1,1} }; queue> q; //깊이 탐색을 위한 큐 visited[sy][sx] = 1; // start 위치 방문 처리 q.push({sy,sx}); while(q.size()) { tie(y,x) = q.front(); q.pop(); for(int i = 0; i < 4 ; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if(ny < 0 || ny >= N || nx < 0 || nx >= M || map[ny][nx] == 0) continue; if(visited[ny][nx]) continue; visited[ny][nx] = visited[y][x] + 1; q.push({ny, nx}); } } printf("%d ", visited[ey][ex]); // 최단거리 디버깅 for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cout << visited[i][j] << ' '; } cout << ' '; } return 0; }

kundol · Answer

안녕하세요 kamin님 ㅎㅎ 저는 입력받는 코드를 따로 만들지 않아서, 크기를 예측할 수 있는 코드여서 5X5 로 정의를 해놓았는데, 왜 오버플로우가 일어나는 지 궁금합니다! >> 오버플로우가 아니라 이 코드 자체가 에러가 떠서 그렇습니다. 혹시 이 코드 컴파일러로부터 에러가 뜨지 않았나요? 이 코드는 int main() { int N = 5; int M = 5; int x,y; int visited[N][M] = {0,}; //방문 노드 다음 부분 때문에 에러가 뜨는 코드입니다. C++에서는 단순한 array를 기반으로 N을 정의해서 동적할당을 하려고 한다면 다른 방법을 사용해야 합니다. 대표적으로 malloc 을 사용합니다. 하지만 그럴 바에는 vector를 기반으로 resize()로 동적할당하시는 것을 추천드립니다. 그래서 저 코드는... // Online C++ compiler to run C++ program online #include using namespace std; const int max_n = 104; int dy[4] = {-1, 0, 1, 0}; int dx[4] = {0, 1, 0, -1}; int main() { int N = 5, M = 5; int x,y; int visited[5][5] = {0,}; //방문 노드 //시작 지점 int sx = 0, sy = 0; //끝 지점 int ex = 0, ey = 4; //MAP int map[5][5] = { {1,0,1,0,1}, {1,1,1,0,1}, {0,0,1,1,1}, {0,0,1,1,1}, {0,0,1,1,1} }; queue> q; //깊이 탐색을 위한 큐 visited[sy][sx] = 1; // start 위치 방문 처리 q.push({sy,sx}); while(q.size()) { tie(y,x) = q.front(); q.pop(); for(int i = 0; i < 4 ; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if(ny < 0 || ny >= N || nx < 0 || nx >= M || map[ny][nx] == 0) continue; if(visited[ny][nx]) continue; visited[ny][nx] = visited[y][x] + 1; q.push({ny, nx}); } } printf("%d ", visited[ey][ex]); // 최단거리 디버깅 for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cout << visited[i][j] << ' '; } cout << ' '; } return 0; } 이렇게 수정하시는게 좋습니다. (올바르게 나옵니다.) 그리고 kamin님 코드리뷰를 좀 드리면요. int main() { int N = 5, M = 5; 지역변수보다는 전역변수를 쓰는게 좋습니다. 해당 부분은 교안내의 다음 부분 참고해주세요. 지역변수 보다는 전역변수를, 변수명을 간결하게. int visited[5][5] = {0,}; //방문 노드 0으로 초기화하는 것은 교안내의 다음부분을 참고해주세요. 쓰지 말아야 할 초기화 방법 {0, } 다른 부분들은 잘 짜셨습니다. ㅎㅎ 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.