글 읽기 - 33%에서 계속 틀렸다고 나오는데 이유를 모르겠습니다....

legionary7931 3년 전 0

초기화도 해줬고, x좌표 y좌표 바뀐거도 다 확인해준거 같은데 당최 틀린 이유를 모르겠습니다. 간단한 dfs라고 생각했는데 안나오니까 너무 화나네요 ㅠㅠ 틀린점 찾아주실 능력자 분 구합니다...

기본적인 아이디어는 1로 된 배추 위치를 시작점으로 해서 dfs를 통해 연결된 배추들을 전부 찾아 2로 바꿔주고 지렁이 count를 올려주는 식입니다.

#include <iostream>
using namespace std;

int testNum;
int M, N, K; // M = 가로, N = 세로, K = 배추 개수
int ground[50][50] = {0, };

void ground_dfs(int y, int x, int M, int N){
    
    if(y < 0 || x < 0 || y > N-1 || x > M-1) return;
    
    if(ground[y+1][x] != 1 && ground[y][x+1] != 1){
        ground[y][x] = 2;
        return;
    } 

    if(ground[y+1][x] == 1){
        ground[y][x] = 2;
        ground_dfs(y+1, x, M, N);
    }
    if(ground[y][x+1] == 1){
        ground[y][x] = 2;
        ground_dfs(y, x+1, M, N);
    }

    return;
}

int main(void){
    scanf("%d", &testNum);

    for(int i = 0; i < testNum; i++){
        scanf("%d %d %d", &M, &N, &K);
        
        for(int a = 0; a < 50; a++){
            for(int b = 0; b < 50; b++){
                ground[a][b] = 0;
            }
        }
        
        int x, y;
        for(int j = 0; j < K; j++){
            scanf("%d %d", &x, &y);
            ground[y][x] = 1;
        }

        int result = 0;
        for(int b = 0; b < N; b++){
            for(int a = 0; a < M; a++){
                if(ground[b][a] == 1) {
                    ground_dfs(b, a, M, N);
                    result++;
                }
            }
        }

        printf("%d\n", result);
    }
}

ghghgh777 3년 전 0

2 2 3

1 0

0 1

1 1

일 때 2가 출력되네요. 답은 1입니다.

legionary7931 3년 전 0

모든 방향으로 dfs를 해줘야 되는데 우측 하단으로만 dfs를 하려고 한 제 실수였네요 ㅎㅎ 감사합니다!

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

문제

문제

출처

ICPC

33%에서 계속 틀렸다고 나오는데 이유를 모르겠습니다....

legionary7931 3년 전 0

ghghgh777 3년 전 0

legionary7931 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말