글 읽기 - 1012번 양배추 문제 재귀에서 Stackoverflow 가 일어납니다 ㅠㅠ 흑

vzorov 7년 전 0

안녕하세요, 1012 번 양배추 문제 코딩을 했는데, Stack overflow 로 컴파일이 진행되지 않습니다 ㅠㅠ
search() 재귀 함수에서 뭔가 오류가 있는것 같은데 제 수준에서 도저히 모르겠어서 질문글 올립니다.
고수님들 한번만 봐주십시오 ㅠㅠ 미리 감사드립니다.

#include <stdio.h>
#define MAX 50
#define MAXI 2500
int num;
int M, N, K;
int cabb[MAX][MAX];
int cnt;
int check[MAX][MAX];
void search(int y, int x) {
    if (cabb[y][x + 1] == 1) {
        check[y][x + 1] = 1;
        search(y, x + 1);
    }
    else if (cabb[y][x - 1] == 1) {
        check[y][x - 1] = 1;
        search(y, x - 1);
    }
    else if (cabb[y - 1][x] == 1) {
        check[y - 1][x] = 1;
        search(y - 1, x);
    }
    else if (cabb[y + 1][x] == 1) {
        check[y + 1][x] = 1;
        search(y + 1, x);
    }
    else return;
}
void BFS() {
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            if (check[y][x] == 1) continue;
            else {
                if (cabb[y][x] == 0) check[y][x] = 1;
                else if (cabb[y][x] == 1) {
                    search(y, x);
                    cnt++;
                }
            }
        }
    }
}
int main() {
    freopen("testcase.txt", "r", stdin);
    int testcase;
    scanf("%d", &num);
    for (testcase = 0; testcase < num; testcase++) {
        
        scanf("%d", &M);
        scanf("%d", &N);
        scanf("%d", &K);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cabb[i][j] = 0;
            }
        }
        cnt = 0;
        for (int i = 0; i < K; i++) {
            int a;
            int b;
            scanf("%d %d", &a, &b);
            cabb[a][b] = 1;
        }
        BFS();
        printf("testcase %d 의 정답 : %d\n", testcase+1, cnt);
    }
    return 0;
}

etaehyun4 7년 전 1

search에서도 check 배열을 확인해 같은 위치가 두번 호출되지 않게 막아야 합니다.

아니면 (y, x) <-> (y, x + 1) 같은 것이 계속 번갈아서 호출되어 Stack Overflow가 발생 가능합니다

vzorov 7년 전 0

정말 감사드립니다.

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

문제

문제

출처

ICPC

1012번 양배추 문제 재귀에서 Stackoverflow 가 일어납니다 ㅠㅠ 흑

vzorov 7년 전 0

etaehyun4 7년 전 1

vzorov 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말