글 읽기 - 유기농 배추 반례좀 찾아주세요 ㅜㅜ

dkpark10 4년 전 0

제 머리론 맞는데...

어디가 문젠지 모르겠습니다

고수님들 도와주세요 ㅜㅜ

제 코드는 테스트 케이스에 대해 배추를 심어놓은 곳에 true로 체크를 하고

배추심어놓은곳을 재귀로 다돌면 false로 체크 더이상 돌 곳이 없을떄

지렁이의 숫자를 출력합니다.

간단히 말해 배열안에서 연결되있는 그래프의 개수를 찾게 짰는데

틀림으로 나오네요 ㅜㅜ

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define MAX 50
using namespace std;
int map[MAX + 1][MAX + 1];
bool check[MAX + 1][MAX + 1];
int dirx[4] = {0, 0, 1, -1}; // 동서남북 x 좌표
int diry[4] = {1 ,-1, 0, 0}; // 동서남북 y 좌표
int T, M, N, K;

void Organic(int x, int y)
{
    if (x >= N || y >= M || x < 0 || y < 0){ // 배열의 가장자리를 벗어나면리턴
        return;
    }
    
    if (map[x][y] == 1){                     // 배추가 심어져있다면

        check[x][y] = false;                 // 체크
        for(int i=0; i< 4; i++){ 
            int nx = x + dirx[i];            // 다음좌표 x       
            int ny = y + diry[i];            // 다음좌표 y

            if(map[nx][ny] == 1 && check[nx][ny] == true){ // 배추가 심어져있고 true라면 
                Organic(nx, ny);                           // 재귀
            }
        }
    }
    map[x][y] = 0;          // 다음 테스트케이스를 위해 맵 초기화
}

int main(void)
{
    int x, y, worm = 0;
    scanf("%d", &T);

    for (int i = 0; i < T; i++){

        worm = 0;                             // 지렁이 초기화
        scanf("%d %d %d", &M, &N, &K);
        for(int i=0; i<K; i++){
            scanf("%d %d", &x, &y);
            map[x][y] = 1;
            check[x][y] = true;             // 배추심어놓은곳 체크
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(check[i][j] == true){   // 지렁이가 돌지않은곳 Orinaic함수가 실행될때마다 
                    Organic(i,j);          // 지렁이 한마리 증가
                    worm++;
                }
            }
        }
        printf("%d\n",worm);
    }

    return 0;
}

seico75 4년 전 0

15줄이 25줄에 들어가고 return이 continue

x y는 nx ny 가 되어야하지.않을까요?

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

문제

문제

출처

ICPC

유기농 배추 반례좀 찾아주세요 ㅜㅜ

dkpark10 4년 전 0

seico75 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말