글 읽기 - 채점에 문제가 있습니다.

cha 5년 전 0

bool visited[26][26] = {0,}; 가 실제로 사용되지 않음에도 정의 유무에 따라서 결과가 달라집니다.

위 선언을 지우거나 위치만 옮겨도 오답이 나는 것으로 보아 문제가 있는 것 같습니다.

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int N;
bool visited[26][26] = {0,}; // <=== 없으면 오답! 위치 바뀌어도 오답!
char mat_char[26][26];
bool mat[26][26];
queue < pair < int, int > > que;
int dr[4] = {1,0,-1,0};
int dc[4] = {0,1,0,-1};
int cnt_house;
int danji_cnt = 0;
vector < int > ans_list;

void bfs(int now_r,int now_c){
    danji_cnt = danji_cnt+1;
    cnt_house = 0;
    que.push(make_pair(now_r,now_c));
    mat[now_r][now_c] = 0;
    
    while(!que.empty()){
        
        int now_r = que.front().first;
        int now_c = que.front().second;
        cnt_house = cnt_house + 1;
        que.pop();
        
        
        // 탐색조건
        for(int i=0;i<4;i++){
            
            int nxt_r = now_r + dr[i];
            int nxt_c = now_c + dc[i];
            
            if(nxt_r<=N && nxt_r >= 1 && nxt_c <= N && nxt_c>=1 && mat[nxt_r][nxt_c] == 1){
                
                que.push(make_pair(nxt_r,nxt_c));
                mat[nxt_r][nxt_c] = 0;
                
            }
        }
    }
}


int main(){
    scanf("%d", &N);     // 입력
    
    for(int i=1;i<=N;i++){
        scanf("%s",&mat_char[i][1]);
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            mat[i][j] = (int)mat_char[i][j] - 48;
        }
    }
    
    
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(mat[i][j] == 1){
                bfs(i,j);
                
                ans_list.insert(ans_list.end(),cnt_house);
                
            }
        }
    }
    printf("%d\n", danji_cnt);
    sort(ans_list.begin(), ans_list.end()); // 정렬
    for(int i=1;i<=danji_cnt;i++){
        printf("%d\n",ans_list[i-1]);
    }
}

djm03178 5년 전 0

그것은 채점에 문제가 있는 것이 아니고, 프로그램이 오작동을 할 여지가 있기 때문에 나는 것입니다.

문제는 54번째 줄입니다. 길이가 25인 문자열을 %s로 입력받으려면 최소 26칸이 필요합니다. 마지막에 널 문자가 들어가기 때문입니다. 인덱스를 1부터 시작하므로 최소 26번째 칸까지는 사용이 가능해야 하는데, mat_char의 크기가 26이므로 인덱스가 25까지밖에 없어서 메모리를 침범하게 됩니다.

이 때 9번째 줄이 어떤 역할을 하느냐면, 이 인덱스가 넘어선 바로 다음 위치가 visited 배열이 되어 그 방파제 역할을 하도록 프로그램이 만들어졌기 때문입니다. 이게 없다면 그 역할은 더 위에 있는 int N이 대신 맞게 되고, 이 때문에 N의 값에 변동이 생겨 잘못된 동작을 한 것으로 예측됩니다.

물론 이것은 추측이 그런 것이고, 실제로는 메모리의 전혀 다른 부분을 건드렸을 수도 있습니다. 확실한 것은, 이 프로그램은 정상적이지 않은 동작을 할 가능성이 있다는 것입니다.

dlwocks31 5년 전 0

Undefined behavior에 대해 알아보세요.

https://en.wikipedia.org/wiki/...

"The implementation will be considered correct whatever it does in such cases,(...) It is the responsibility of the programmer to write code that never invokes undefined behavior."

댓글을 작성하려면 로그인해야 합니다.