글 읽기 - 예시 반례 다 맞게 나오는데 틀렸다고 나와서요ㅠㅠ

doded12 3년 전 0

안녕하세요, bfs를 이용해서 처음엔 array 배열에 무리 번호를 입력하고

check배열에는 원래 배열 그대로 저장하고 cnt 배열에는 각 무리에 해당하는 0의 갯수를 저장하였습니다.

다시 이중for문을 돌리면서 check배열(원래 배열)이 1이면 상하좌우의 무리를 조사해 그 무리에 해당하는 0의 갯수를 더해 출력하는 방식으로 코드를 구현했습니다.(무리를 겹쳐서 더하게될까봐 역시 해당무리를 더했는지 ch배열로 체크해주었습니다)

예시와 반례 다 적용하면 다 맞게나오는 것 같은데 채점하면 몇%로 가는 것도 없이 그냥 틀려버려서요..

혹시 제가 틀린 부분이 있다면 알려주세요 부탁드립니다ㅠㅠ

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

queue<pair<int,int> > q;
int n, m, k, a, b, x, y, x_n, y_n, hap=0, res, p=1, dap=0, x_p, y_p;
int array[1002][1002]={0};	bool check[1002][1002]={0}; int cnt[500002]={0}; int ch[500002]={0};
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
int bfs(int p) //array 배열에 0의 위치에 무리 번호 저장하기 
{
	while(!q.empty())
	{
		x=q.front().first; 
		y=q.front().second;
		q.pop();
		for(int i=0;i<4;i++)
		{
			x_n=x+dx[i];
			y_n=y+dy[i];
			if(x_n>=1 && x_n<=n && y_n>=1 && y_n<=m && !array[x_n][y_n])
			{
				q.push(make_pair(x_n,y_n));
				array[x_n][y_n]=p;
				hap++; 
			}	
		}
	}
	cnt[p]=hap; // cnt배열에 p번째 무리의 수 저장하기 
	return p;
}
/*bfs결과
1 0 0 1 1
1 1 0 1 0
0 0 1 0 1
1 0 1 0 0
의 원본 배열이
1 2 2 1 1
1 1 2 1 3
4 4 1 5 1
1 4 1 5 5
로 바뀜(무리 번호 저장하기) 
*/	
int main()
{
	freopen("input.txt", "rt", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>res;
		for(int j=m;j>=1;j--)
		{
			array[i][j]=res%10;
			if(array[i][j]==1) check[i][j]=1; //check배열에 원본 그대로 복사해놓기 
			res=res/10;
		}
	}
	for(int i=1;i<=n;i++)////무리 조사해서 ARRAY에 입력하기(무리 번호) 
	{
		for(int j=1;j<=m;j++)
		{
			if(array[i][j]==0)
			{
				p++;
				hap=1;
				array[i][j]=p;
				q.push(make_pair(i,j));
				p = bfs(p);
			}
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(check[i][j]==0) //원래 배열이 0이면 그대로 0출력 
			{
				cout<<check[i][j];
			}
			if(check[i][j]==1)// 벽 깨부시고 상하좌우 방향으로 저장되어있는 무리 번호의 갯수 합치기  
			{
				dap=0;
				for(int d=0;d<4;d++) 
				{
					x_p=i+dx[d];
					y_p=j+dy[d];
					if(x_p>=1 && x_p<=n && y_p>=1 && y_p<=m && array[x_p][y_p]!=1 && ch[  array[x_p][y_p] ]==0 )
					{
						dap+=cnt[ array[x_p][y_p] ];
						ch[  array[x_p][y_p]  ]=1;  	
					}
				}
				cout<<(dap+1)%10;
			}
			for(int i=2;cnt[i]!=0;i++) ch[i]=0;
			//cout<<endl;
		}
		cout<<endl;
	}
	return 0; 
}

dldyddlwl 3년 전 0

freopen("input.txt", "rt", stdin);가 문제인 것 같습니다.

doded12 3년 전 0

앗 당연히 저부분은 제외하고 제출했습니다ㅠㅠ혼란을 드려 죄송합니다..

dldyddlwl 3년 전 2

여기서 res를 받는 과정에서, 행과 열이 1000개까지 주어질 수 있잖아요?

그렇다면, 예를 들어, 11111111111111111111111111111111111111111111... 11111111111 이라면, res는 int형이므로, 이 값을 받아낼 수가 없습니다!

for(int i=1;i<=n;i++)
{
		cin>>res;
		for(int j=m;j>=1;j--)
		{
			array[i][j]=res%10;
			if(array[i][j]==1) check[i][j]=1; //check배열에 원본 그대로 복사해놓기 
			res=res/10;
		}
}

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

문제

문제

출처

ICPC

예시 반례 다 맞게 나오는데 틀렸다고 나와서요ㅠㅠ

doded12 3년 전 0

dldyddlwl 3년 전 0

doded12 3년 전 0

dldyddlwl 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말