글 읽기 - 테스트 케이스는 다 맞지만 채점은 틀리네요ㅠㅜ

shady 5년 전 0

안녕하세요!

큐 혹은 BFS에 대한 이해가 조금 부족한 상태에서 뻘짓을 했습니다..

뻘짓이었지만 어찌어찌 테스트케이스는 다 맞았는데 채점하면 틀렸다고 나옵니다. 이유를 도저히 모르겠더라고요.

약간 소스가 더러운 느낌은 있는데..혹시 살펴봐주실 수 있다면 정말 감사드리겠습니다.

부끄러운 코드입니다..큐에 반복문을 쓰고..순차적으로 반복문을 쓰려고 하다 보니

인덱스로 꼼수도 부렸네요.

나중에 소스 뜯어 고쳐서, 반복문 없이 큐를 사용해서 맞았습니다만,

처음 작성한 코드가 왜 틀렸는지 꼭 알고 싶습니다.

댓글이 아예 안 달릴 수도 있지만, 시간 내어 답변 달아주신 분께 미리 감사드립니다!!

#include <iostream>
#include <queue>
using namespace std;
int BFS();
int N, M;
int box[1003][1001];
bool visited[1001][1001];
int w_around[4] = {1, 0, -1, 0};
int h_around[4] = {0, 1, 0, -1};
vector<pair<int, int>> coord; // 값이 1인 좌표 담기

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 1; i <= M; ++i)
		for (int j = 1; j <= N; ++j)
		{
			cin >> box[i][j];
			if (box[i][j] == 1)
				coord.emplace_back(make_pair(i, j));
		}

	int cnt = BFS();
	bool flag = false;
	for (int i = 1; i <= M; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			if (box[i][j] == 0)
			{
				flag = true;
				break;
			}
		}
		if (flag)
			break;
	}
	if (flag)
		cout << -1 << '\n';
	else
		cout << cnt << '\n';
}

int BFS()
{
	queue<pair<pair<int, int>, int>> q[1001]; // BFS 단계까지 저장(최우측)
	int size = coord.size();
	int z = 0;

	int idx = 0;
	for (size_t i = 0; i < size; ++i)
	{
		int x = coord.back().first;
		int y = coord.back().second;
		coord.pop_back();
		q[i].push(make_pair(make_pair(x, y), 0));
	}
	while (!q[idx].empty())
	{
		int w = q[idx].front().first.first;
		int h = q[idx].front().first.second;
		z = q[idx].front().second;
		q[idx].pop();
		if (box[w][h] = 1 && visited[w][h] == false)
		{
			visited[w][h] = true;
			for (int i = 0; i < 4; ++i)
			{
				int ww = w + w_around[i];
				int hh = h + h_around[i];
				if (box[ww][hh] == 0 && visited[ww][hh] == false
					&& ww > 0 && hh > 0 && ww <= M && hh <= N)
				{
					box[ww][hh] = 1;
					q[idx].push(make_pair(make_pair(ww, hh), z+1));
				}
			}
		}		
		if (q[++idx %= size].empty())
			++idx%=size;
	}
	return z;
}

shady 5년 전 0

// rms

반례가 있군요!! 역시 지저분한 코드는..ㅜ

감사합니다.

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

문제

문제

출처

ICPC

테스트 케이스는 다 맞지만 채점은 틀리네요ㅠㅜ

shady 5년 전 0

shady 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말