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

작성한 질문수 7

1

안녕하세요 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 <bits/stdc++.h>
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<pair<int, int>> 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\n", visited[ey][ex]); 
    // 최단거리 디버깅 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
        	cout << visited[i][j] << ' '; 
        }
        cout << '\n';
    } 

    return 0;
}
 

이렇게 수정하시는게 좋습니다. (올바르게 나옵니다.)

그리고 kamin님 코드리뷰를 좀 드리면요.

int main() { 
    int N = 5, M = 5; 

지역변수보다는 전역변수를 쓰는게 좋습니다.

해당 부분은 교안내의 다음 부분 참고해주세요.

지역변수 보다는 전역변수를, 변수명을 간결하게.

    int visited[5][5] = {0,}; //방문 노드

0으로 초기화하는 것은 교안내의 다음부분을 참고해주세요.

쓰지 말아야 할 초기화 방법 {0, }

다른 부분들은 잘 짜셨습니다. ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.