글 읽기 - 100X100 격자를 DFS 할때 stackoverflow 나는 문제

sgc109 8년 전 0

입력이 첫째줄에 100 그다음줄에 R 이 만개들어갈때

서브함수호출이 1만번 돼서 스택이 꽉차서오버플로우 뜨는건가요?

이런문제는 어떻게 해결하나요..?

#define REP(i,a,b) for(int i = a; i < b;++i)
#define FOR(i,n) REP(i,0,n)

#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<stack> 
#include<queue>
#include<string.h>


using namespace std;

vector<vector<char>> map;
vector<vector<char>> map_weird;

int dir_x[4]={-1,0,0,1};
int dir_y[4]={0,-1,1,0};

int N;

void dfs(int ii,int jj, vector<vector<char>> &v) {
    char backup = v[ii][jj];
    v[ii][jj] = 0;
    FOR(i,4) {
        if(ii+dir_y[i] >= 0 && ii+dir_y[i] < N && jj+dir_x[i] >=0 && jj+dir_x[i] <N && v[ii+dir_y[i]][jj+dir_x[i]] == backup) {
            dfs(ii+dir_y[i],jj+dir_x[i],v);
        }
    }
}

int main() {
    scanf("%d",&N);
    map = vector<vector<char>>(N,vector<char>(N,0));
    map_weird = vector<vector<char>>(N,vector<char>(N,0));
    
    FOR(i,N) {
        FOR(j,N) {
            char tmp;
            scanf(" %c",&tmp);
            map[i][j] = tmp;
            if(tmp == 'R') tmp = 'G';
            map_weird[i][j] = tmp;
        }
    }
    
    int cnt=0;
    int cnt_weird=0;
    FOR(i,N) {
        FOR(j,N) {
            if(map[i][j] != 0) {
                dfs(i,j,map);
                ++cnt;
            }
            if(map_weird[i][j] != 0) {
                dfs(i,j,map_weird);
                ++cnt_weird;
            }
        }
    }
    
    printf("%d %d",cnt,cnt_weird);
    
    return 0;
}