글 읽기 - [C] DFS풀이 반례 또는 틀린 부분 찾아주시면 감사하겠습니다.

developer_2021 1년 전 0

안녕하세요,

DFS 풀이로 접근했습니다.

예제는 맞게 나왔지만 '틀렸습니다'로 출력되어 반례 부탁드립니다.

감사합니다!

#if 01
#include <stdio.h>
int map[100][100]={0,};
int map_copy[100][100]={0,};
int N;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int cnt;
int scale = 0;
int M = -1;
int max = -1;
void init(void){
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            map[i][j] = map_copy[i][j];
        }
    }
}

void DFS(int x, int y, int scale){
    map[x][y] = 0; // visit배열 사용 대신에 map[i][j] = 0으로 만들어서 중복 없애기
    
    for(int w=0; w<4; w++){
    if(map[x+dx[w]][y+dy[w]] > scale){
            DFS(x+dx[w], y+dy[w], scale);
        }
    }
}

int main(void){
    
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            scanf("%d", &map[i][j]);
            if(M < map[i][j]) M = map[i][j]; // 가장 큰 높이(map[i][j])를 M으로 설정
            map_copy[i][j] = map[i][j];
        }
    }
    while(scale <= M){ // 가장 큰 높이 숫자만큼 반복. scale은 수면 높이(0~M까지). 
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(map[i][j] > scale){
                    DFS(i, j, scale);
                    cnt++;
                }
            }
        }
        if(cnt > max){ //cnt = 물에 잠기지 않은 섬 개수
            max = cnt;
        }
        cnt = 0; //cnt 초기화
        init(); // map[i][j] 초기화
        scale++;
    }
    printf("%d\n", max);
    
    return 0;
}

#endif

yhj1937 1년 전 1

DFS 돌릴 때 x, y 범위를 체크하지 않아서 주어진 범위 밖을 참조하는 것 같습니다.

developer_2021 1년 전 1

감사합니다. 해결되었습니다!

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

문제

문제

출처

ICPC

[C] DFS풀이 반례 또는 틀린 부분 찾아주시면 감사하겠습니다.

developer_2021 1년 전 0

yhj1937 1년 전 1

developer_2021 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말