글 읽기 - 2583 질문드려요!! (반례, 코드 오류 찾아주세요!!)

uss425 5년 전 0

테스트 케이스 여러개 넣고 다 해봤는데 다 잘되지만.. 제출을 하면 틀렸다고 뜨네요 ㅠㅠ

반례나 코드에 대한 오류 좀 찾아주세요 ㅠㅠ

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int board[101][101]; //1은 벽, 0은 탐색가능, 2는 탐색완료 
int M, N, K, answer=0; 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,-1,1};
int S[101]; vector<int> S1;
vector<pair<int, int> > P;

//입력된 좌표값을 바탕으로 배열을 갱신한다
void AdjBoard()   
{	
	for(int i=0; i<=P.size(); i++)
	{
		int y1=P.back().first; int x1=P.back().second;
		P.pop_back();
		int y2=P.back().first; int x2=P.back().second;
		P.pop_back();
				
		for(int i=y2; i<y1; i++)
		for(int j=x2; j<x1; j++)
			board[i][j]=1;		
	}
}

//DFS를 진행한다 
void DFS(int y, int x)
{
	if(y<0 || x<0 || y>=M|| x>=N) return;
	if(board[y][x]!=0)	return;
	
	board[y][x]=2; //탐색 완료된 칸은 2이다. 
	S[answer]++; //넓이를 1 증가한다. 
	
	for(int i=0; i<4; i++)
	{
		int ny=y+dy[i];
		int nx=x+dx[i];
		
		DFS(ny, nx); 
	}
}

int main()
{
	cin>>M>>N>>K;
	
	for(int i=0; i<K; i++)
	{
		int y, x;
		for(int j=0; j<2; j++)
		{
			cin>>x>>y;
			P.push_back(make_pair(y, x));
		}
	}
	
	AdjBoard();
	
	for(int i=0; i<M; i++)
	for(int j=0; j<N; j++)
	if(board[i][j]==0)
	{
		DFS(i, j);
		answer++;
	}
		
	cout<<answer<<endl;
	
	/* 배열에 저장된걸 벡터로 옮겨 sort한 뒤 출력*/ 
	for(int i=0; i<answer; i++)
		S1.push_back(S[i]);
	sort(S1.begin(), S1.end());
	for(int i=0; i<answer; i++)
		cout<<S1[i]<<' ';	
}

djm03178 5년 전 0

18번째 줄은 무슨 의도인가요? 루프가 굉장히 이상한 동작을 하게 될 것입니다. P.size()는 매 루프마다 2씩 줄어드는데, i는 1씩 증가하고, 대략 P가 처음 크기의 1/3 정도가 됐을 때 루프를 빠져나가겠네요.

uss425 5년 전 0

해당 코드만 수정해주니 바로 정답처리가 되네요 ㅠㅠ

감사합니다!!~

while(!P.empty())
{
	int y1=P.back().first; int x1=P.back().second;
	P.pop_back();
	int y2=P.back().first; int x2=P.back().second;
	P.pop_back();
			
	for(int i=y2; i<y1; i++)
	for(int j=x2; j<x1; j++)
		board[i][j]=1;		
}

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

문제

문제

출처

ICPC

2583 질문드려요!! (반례, 코드 오류 찾아주세요!!)

uss425 5년 전 0

djm03178 5년 전 0

uss425 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말