글 읽기 - 배추밭 문제 질문 입니다. 어디서 틀린걸까요? 알고리즘 적어봤습니다.

alsghdjrk 5년 전 0

메인에서 테스트 케이스 갯수를 받고
테스트 케이스 받으면 1개 줄이고 좌표들을 다 입력받고
밭을 0으로 전부 초기화
받은 좌표로 받을 채우고
벌레와 시작좌표를 0으로 초기화
만약 받에 배추가 있을때 bfs실행 (제가 한게 bfs가 맞나요?)
bfs를 실행할때는 밭을 0으로 바꿔주고(다시 방문하는 일이 없도록) 4방향 을 방문한다
한번의bfs1(배추를 발견하면)를 실행하면 warm 카운트를 1개 올리고
y가 col의 갯수를 넘으면 0으로 바꾸고 x를 1개 올려준다
x가 행의 갯수와 같거나 커지면 빠져나온다

테스트 케이스는 잘돌아가고 몇개의 케이스를 만들어서 돌려봤는데도 잘 돌아갑니다...

출력형식도 맞춰서 했고요

혹시 반례가 되는 테스트 케이스나 틀린 부분지적해 주시면 감사드립니다.

#include<iostream>
#include<vector>
using namespace std;

int farm[50][50];
vector <pair <int, int > > v1;

struct testcase{
	int row;
	int col;
	int cabbage;
};

void bfs(int x, int y){
	if(farm[x][y] ==1){
	farm[x][y] =0; // 숫자를 0으로 바꿔주고
	bfs(x+1,y); // 4개면에 대해 실행;
	bfs(x-1,y);
	bfs(x,y+1);
	bfs(x,y-1);
	}
}

int bfs1(int row,int col,int cabbage){
	for(int i=0;i<50;i++){
		for(int j=0;j<50;j++){
			farm[i][j] =0;
		}
	}//0으로 초기화
	for(int i=0;i<cabbage;i++){
		farm[v1[i].first][v1[i].second] =1;
	} // 맵을 채우고
	int warm =0;//벌레 초기화
	int x=0,y=0;// 좌표 초기화
	while(1){
		if(farm[x][y] == 1){
			warm +=1;
			bfs(x,y);
		}
		if(farm[x][y] == 0){
			if(y<col)y++;
			else{
				x++;
				y =0;
			}
			if(x>=row)
				return warm;
		}
	}
}

int main(){
	int t;
	cin>> t;
	testcase Temp;

	while(t>=1){
		t--;//테스트 케이스를 줄이고 실행
		cin>> Temp.row >> Temp.col >> Temp.cabbage;
		int x,y;
		for(int i=0;i<Temp.cabbage;i++){
			cin>> x>>y;
			v1.push_back(make_pair(x,y));
		}
		cout<<bfs1(Temp.row,Temp.col,Temp.cabbage)<<"\n";
		v1.clear();

	}
}

djm03178 5년 전 1

bfs 함수에 배열의 범위를 벗어난 좌표가 들어오면 어떻게 될까요?

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

문제

문제

출처

ICPC

배추밭 문제 질문 입니다. 어디서 틀린걸까요? 알고리즘 적어봤습니다.

alsghdjrk 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말