글 읽기 - bfs사용 테스트 통과, 채점 실패입니다.

wferel 4년 전 0

dfs로 푼 후 bfs사용하여 문제를 풀고싶어서 bfs로 문제를 풀어봤습니다. bfs함수는 일반적인 bfs함수입니다.

main문에서는 상하좌우로 인접한 인덱스를 찾아서 그래프로 엮어줬습니다.

예로

input

1 1

1 0

의 경우에

1 2

3 4

이렇게 4개의 노드가 있다고 하여 1,2,3 노드들을 엮어주었고 bfs돌며 check[i]=1로 체크하여 check[i]=0 이고 노드가 1 (0이면 단지가 아니기 때문)인 경우에 bfs를 돌게끔 하였습니다.

arr배열은 bfs돌며 노드의 개수를 카운트하여 저장하는데 사용하였습니다.

질문 그대로 테스트는 통과하는데 채점하면 실패합니다. 어디가 잘못된건지 잘 모르겠습니다!

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int answer = 0;;
int visit[630];
int check[630];
vector<int> arr = { 0 };
int num = 0;
vector<int> old_graph[630];
vector<int> graph[630];

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visit[start] = true;
	while (!q.empty())
	{
		int x = q.front(); q.pop();
		arr.back()++;
		for (int i = 0; i< graph[x].size(); i++)
		{
			int y = graph[x][i];
			if (!visit[y])
			{
				q.push(y);
				visit[y] = true;
				check[y] = 1;
			}
		}
	}
}
int main(void)
{ 
	int n, m;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int n1;
		for (int j = 0; j < n; j++)
		{
			scanf("%1d", &n1);
			old_graph[i].push_back(n1);
		}
	}
	int directX[] = { -1, 1, 0, 0 };
	int directY[] = { 0, 0, -1, 1 };
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (old_graph[i][j] == 1)
			{
				for (int k = 0; k < 4; k++)
				{
					int nextX = i + directX[k];
					int nextY = j + directY[k];
					if (nextX < 0 || nextX == n || nextY < 0 || nextY == n) {
						continue;
					}
					else if (old_graph[nextX][nextY] == 1)
					{
						graph[i*n+j+1].push_back(nextX*n+nextY+1);
						graph[nextX*n + nextY+1].push_back(i*n + j+1);
					}
				}
			}
		}
	}
	
	for (int i = 1; i <= n*n; i++)
	{
		if (check[i] == 0 && graph[i].size()>0)
		{
			bfs(i);
			answer++;
			num++;
			arr.push_back(0);
		}
	}
	cout << answer<<"\n";
	sort(arr.begin(), arr.end());
	for (int i = 1; i < arr.size(); i++)
		cout << arr[i]<<"\n";
	/**/
	return 0; 
}

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

문제

문제

출처

ICPC

bfs사용 테스트 통과, 채점 실패입니다.

wferel 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말