글 읽기 - dfs로 풀었는데 반례좀 찾아주세요

predy 1년 전 0

바로 틀렸다고 나와요 게시판에 있는거 다 되는거 같은데..

#include<stdio.h>
#include<stdlib.h>

int matrix[101][101]={0};	
int visited[101][101]={0};
int ans[101]={0};

int dx[4]={0, 0, 1, -1};
int dy[4]={1, -1, 0, 0};

void dfs(int n, int m, int h){
	int i;
	visited[n][m]=1;
	//printf("[%d, %d] ", n, m);
	for(i=0;i<4;i++){
		if((visited[n+dx[i]][m+dy[i]]==0) && (matrix[n+dx[i]][m+dy[i]]>h)){
			dfs(n+dx[i], m+dy[i], h);
		}
	}
}

void init(int n){
	int i, j;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			visited[i][j]=0;
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			matrix[i][j]=0;
		}
	}
}

int main(){
	int n, m, i, j, k=0, h, max=0;
	k=0;
	scanf("%d", &n);
	for(i=0;i<n;i++){
		for(j=0; j<n; j++){
			int num;
			scanf("%d", &num);
			if(num>max){
				max=num;
			}
			matrix[i][j]=num;
		}
	}
	for(h=0; h<=max; h++){ //높이0부터 max까지 
		init(n);
		//printf("[%d : ", h);
		for(i=0; i<n; i++){
			for(j=0; j<m; j++){
				if((matrix[i][j]>h) && (visited[i][j]==0)){
					dfs(i, j, h);
					ans[h]++;
					//printf("ans[%d]:%d ", h, ans[h]);
				}
			}
		}
		//printf("]\n");
	}
	k=0;
	for(i=0;i<h;i++){ //정답배열중에 가장큰수 
		if(ans[i]>k){
			//printf("ans[%d]=%d\n", i, ans[i]);
			k=ans[i];
		}
	}
	printf("%d", k);
	return 0;
}

dae0102528 1년 전 0

init(int n) 함수에서 입력받은 배열까지 싹다 초기화 하고 있네요...

predy 1년 전 0

막 수정하다가 이상한걸 건드렸네요 아래부분 빼고해도 바로 틀렸다고 나와요

for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			matrix[i][j]=0;
		}
	}

dae0102528 1년 전 0

간단한 오타네요 ㅎㅎ;

54번 줄에 뜬금없이 m이 있습니다. 풀이는 맞는 거 같아요.

predy 1년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

dfs로 풀었는데 반례좀 찾아주세요

predy 1년 전 0

dae0102528 1년 전 0

predy 1년 전 0

dae0102528 1년 전 0

predy 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말