글 읽기 - 어디서 틀렸는지 도저히 모르겠습니다...

yh9468 6년 전 0

BFS로 문제를 풀었는데 제가 생각해본 간단한 예제들은 다 맞는데 답은 틀리다고 나오네요... 어디서 틀렸는지 알려주시면 감사하겠습니다!

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

bool friends[50][50];
int check[50][50] = {};

int max(int a, int b)
{
	return a > b ? a : b;
}

int main()
{
	int number;
	string input;
	cin >> number;
	for (int i = 0; i < number; i++)
	{
		cin >> input;
		for (int k = 0; k < number; k++)
		{
			if (input[k] == 'N')
				friends[i][k] = 0;
			else
				friends[i][k] = 1;
		}
	}
	int answer = 0;
	for (int i = 0; i < number; i++)
	{
		queue<pair<int, int> >q;
		pair<int, int> temp(i, 0);
		q.push(temp);
		while (!q.empty())
		{
			int first = q.front().first;
			int second = q.front().second;
			for (int k = 0; k < number; k++)
			{
				if (friends[first][k] == 1&& second<=2)
				{
					if (i != k)
					{
						check[i][k] = 1;
						pair<int, int> temp2(k, second + 1);
						q.push(temp2);
					}
				}
			}
			q.pop();
		}
	}
	for (int i = 0; i < number; i++)
	{
		int temp3 = 0;
		for (int k = 0; k < number; k++)
		{
			temp3 += check[i][k];
			answer = max(temp3, answer);
		}
	}
	cout << answer;
	return 0;
}

djm03178 6년 전 1

second가 0일 때, 1일 때, 2일 때 총 3단계에 걸쳐서 체크하기 때문에 2-친구가 아니라 3-친구를 구하고 있습니다.

아래 케이스의 답은 4입니다.

7
NYNNNNN
YNYNNNN
NYNYNNN
NNYNYNN
NNNYNYN
NNNNYNY
NNNNNYN

yh9468 6년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

어디서 틀렸는지 도저히 모르겠습니다...

yh9468 6년 전 0

djm03178 6년 전 1

yh9468 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말