글 읽기 - 반례가 궁금합니다.

gusdnr9875 3년 전 0

반례와 혹시 가능하시다면 왜 틀린지 까지도 부탁드립니다.

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

queue <int> xloc;
queue <int> yloc;
int arr[53][53] = { 0 };

void bfs(int x, int y)
{
	
	
	arr[y][x] = 0; //도착한 지점은 0으로 

	if (arr[y][x + 1] == 1) { //옆에 애가 1이면 걔를 큐에 넣어놓기 ㅎ
		xloc.push(x + 1);
		yloc.push(y);
	}
	if (arr[y+1][x ] == 1) { //아래 애가 1이면 걔를 큐에 넣어놓기 ㅎ
		xloc.push(x);
		yloc.push(y + 1);
	}

	while (xloc.size() != 0)
	{
		int xx = xloc.front(), yy = yloc.front();
		xloc.pop(), yloc.pop();
		bfs(xx, yy);
		
	}
	
}

int main()
{
	int t = 0, m = 0, n = 0, k = 0, x = 0, y = 0;

	cin >> t;

	while (t--) 
	{
		cin >> m >> n >> k;
		int count = 0;

		for (int i = 0; i < k; i++)
		{
			cin >> x >> y;
			arr[x][y]=1;
		}
		
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++) 
			{
				if (arr[i][j] == 1)
				{
					bfs(j, i);
					count++;
				}
			}
		}
		cout << count << '\n';
	}
}

gusdnr9875 3년 전 0

아 그렇네요 유모양이라면 카운트를 해주지않는 경우가 생기네요 감사합니다.

gusdnr9875 3년 전 0

메모리 초과가 나는데 어떻게 하면 좋을까요?

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

queue <int> xloc;
queue <int> yloc;
int arr[53][53] = { 0 };

void bfs(int x, int y)
{


	arr[y][x] = 0; //도착한 지점은 0으로 

	if (arr[y][x + 1] == 1) { //옆에 애가 1이면 걔를 큐에 넣어놓기 ㅎ
		xloc.push(x + 1);
		yloc.push(y);
	}
	if (arr[y + 1][x] == 1) { //아래 애가 1이면 걔를 큐에 넣어놓기 ㅎ
		xloc.push(x);
		yloc.push(y + 1);
	}
	if (arr[y -1][x] == 1) { 
		xloc.push(x);
		yloc.push(y - 1);
	}
	if (arr[y][x-1] == 1) { 
		xloc.push(x-1);
		yloc.push(y );
	}

	while (xloc.size() != 0)
	{
		int xx = xloc.front(), yy = yloc.front();
		xloc.pop(), yloc.pop();
		bfs(xx, yy);

	}

}

int main()
{
	int t = 0, m = 0, n = 0, k = 0, x = 0, y = 0;

	cin >> t;

	while (t--)
	{
		cin >> m >> n >> k;
		int count = 0;

		for (int i = 0; i < k; i++)
		{
			cin >> x >> y;
			arr[x+1][y+1] = 1;
		}

		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				if (arr[i][j] == 1)
				{
					bfs(j, i);
					count++;
				}
			}
		}
		cout << count << '\n';
	}
}

jh05013 3년 전 0

https://www.acmicpc.net/blog/v...

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

문제

문제

출처

ICPC

반례가 궁금합니다.

gusdnr9875 3년 전 0

gusdnr9875 3년 전 0

gusdnr9875 3년 전 0

jh05013 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말