글 읽기 - 2583번 질문이요!!

lllllllhisll 5년 전 0

bfs사용 했구여 틀린곳을 못찾겟어서 질문드립니다.

답이 실제답보다 조금 크게나오네요 ㅠㅠ

부탁드립니다!

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

int m, n,k;
int arr[100][100] = {};
int visited[100][100] = {};
int col[4] = {0,0,-1,1};
int row[4] = { -1,1,0,0 };
int sum;
vector<int> v;

void bfs(int x, int y)
{
	queue<pair<int, int>> q;
	q.push({ x,y });

	while (!q.empty())
	{
		int cx = q.front().first;
		int cy = q.front().second;

		q.pop();
		
		visited[cx][cy] = 1;
		sum++;
		for (int i = 0; i < 4; i++)
		{
			int nx = cx + col[i];
			int ny = cy + row[i];

			if (nx >= 0 && ny >= 0 && nx < m&&ny < n&&!arr[nx][ny] && !visited[nx][ny])
				q.push({ nx,ny });
		}
	}
}

int main()
{
	cin >> m >> n >> k;
	for (int i = 0; i < k; i++)
	{
		int X1, Y1, X2, Y2;
		cin >> Y1 >> X1 >> Y2 >> X2;

		for (int i = X1; i<X2; i++) 
			for (int j = Y1; j<Y2; j++) 
				arr[i][j] = 1;
	}
	
	for(int i=0;i<m;i++)
		for (int j = 0; j < n; j++)
		{
			if (!visited[i][j] && !arr[i][j])
			{
				sum = 0;
				bfs(i, j);
				v.push_back(sum);
			}
		}

	sort(v.begin(), v.end());
	cout << v.size() << "\n";

	for (int i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << "\n";
	
	return 0;
}

lllllllhisll 5년 전 0

while (!q.empty())
{
int cx = q.front().first;
int cy = q.front().second;

q.pop();
**********if (visited[cx][cy] == 1) continue;

visited[cx][cy] = 1;
sum++;
for (int i = 0; i < 4; i++)
{
int nx = cx + col[i];
int ny = cy + row[i];

if (nx >= 0 && ny >= 0 && nx < m&&ny < n&&!arr[nx][ny] && !visited[nx][ny])
q.push({ nx,ny });
}
}

혹시나해서 ****되어있는부분을 추가했더니 정답으로 뜨네요 혹시 무슨차이가있을까요...

어차피 이중포문에서 들어올때나 while문 안에 if문에서 push될때 visited값이 0인 좌표가 들어오지않나요...???

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

문제

문제

출처

ICPC

2583번 질문이요!!

lllllllhisll 5년 전 0

lllllllhisll 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말