글 읽기 - 1113 수영장 만들기 질문있습니다!

gudehd231 3년 전 0

기존 코드의 dfs 와 아래 추가된 dfs 코드가 같은 동작을 한다고 생각하는데,

위에 코드로 제출하면 런타임 에러가 뜨네요...

어떤 부분에서 다르게 동작하는지 알려주시면 감사하겠습니다..!

#include <stdio.h>
#include <algorithm>
using namespace std;

int N,M;
char arr[55][55];
bool visited[52][52];
bool visited2[52][52];
int A[4] = {0,0,1,-1};
int B[4] = {1,-1,0,0};
bool leak;
int dap;
void init(){
	for(int i=0; i<52; i++){
		for(int j=0; j<52; j++)
		visited[i][j] = false;
	}
}
void dfs(int a, int b,int val){
    if(!leak)
        return;
	visited[a][b] = true;
	dap += (val -(arr[a][b]-'0'));
	for(int i=0; i<4; i++){
		int x = a + A[i];
		int y = b + B[i];
		if(x<0 || x >=N || y <0 || y >=M){
				leak = 0;
				return;
		}
		if(leak && visited[x][y] == false && (arr[x][y] -'0') <val){
			dfs(x,y,val);
		}
	}
}
void dfs2(int a, int b, int val){
	visited2[a][b] =true;
	for(int i=0; i<4; i++){
		int x = a + A[i];
		int y = b + B[i];
		//if(x<0 || x >=N || y <0 || y >=M) continue;
		if(!visited2[x][y] && (arr[x][y] -'0')<val)
		dfs2(x,y,val);

	}
}
// void fill(int val){
// 	for(int i=0; i<N; i++){
// 		for(int j=0; j<M; j++){
// 			if(visited[i][j]){
// 				//printf("%d %d---- st \n",dap,arr[i][j]-'0');
// 				dap += val - (arr[i][j]-'0');
// 				//printf("%d ----- ed \n",dap);
// 				//printf("%c ----?\n",char(val+'0'));
// 				arr[i][j] = char(val+'0');
// 			}
// 		}
// 	}
// }

int main(){
	//freopen("input.txt","r",stdin);
	scanf("%d%d",&N,&M);
	for(int i=0; i<N; i++)
	scanf("%s",&arr[i]);
	int ans =0;
	for (int w = 9; w >= 2; w--){
		init();
		for (int i = 0; i < N; i++){
			for (int j = 0; j < M; j++){
				if(visited2[i][j]) continue;
				if (visited[i][j] == false && (arr[i][j] - '0') < w){
					leak = true;
					dap = 0;
					dfs(i, j, w);
					//printf("end -> %d\n",leak);
					if (leak){
						ans += dap;
						dfs2(i,j,w);
					}
				}
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}



/* Pass 되는 dfs */
void dfs(int a, int b,int val){
	if (a<0 || a>=N || b<0 || b>=M) { leak = false; return; }
	visited[a][b] = true; dap += (val -(arr[a][b]-'0'));
	if (arr[a - 1][b] -'0'<val && !visited[a - 1][b]) dfs(a - 1, b, val);
	if (arr[a + 1][b] -'0'<val && !visited[a + 1][b]) dfs(a + 1, b, val);
	if (arr[a][b - 1] -'0'<val && !visited[a][b - 1]) dfs(a, b - 1, val);
	if (arr[a][b + 1] -'0'<val && !visited[a][b + 1]) dfs(a, b + 1, val);
}

shw2495 3년 전 0

https://www.acmicpc.net/board/view/13484 이 답변이 도움이 될 것 같습니다.

일단, 두 코드 모두 음수 인덱스에 접근하게 됩니다. (윗코드는 dfs2, 아랫코드는 dfs1 + dfs2)

근데 윗코드는 dfs2만 음수 인덱스에 접근하니 visited2의 주변 상태에 따라 런타임에러가 나는 것 같습니다.

+ 음수 인덱스로 접근 못하게 하면 오답이 뜨네요.

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

문제

문제

출처

ICPC

1113 수영장 만들기 질문있습니다!

gudehd231 3년 전 0

shw2495 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말