글 읽기 - 2146번 C++ 코드 100%에서 틀렸다고 뜹니다. 반례좀 알려주세요..ㅠㅠ

mycool0905 5년 전 0

제 코드를 예를 들어서 간략하게 설명할게요

1 1 0 0 1

1 0 0 0 0

0 0 0 0 0

1 0 0 0 0

1 0 0 1 1

이렇게 입력을 받았으면

devide_field() 함수로

2 2 0 0 3

2 0 0 0 0

0 0 0 0 0

4 0 0 0 0

4 0 0 5 5

field가 이렇게 되고,

BFS의 시작점을 저장해놓는 큐인 store는

(0,1), (0,4), (1, 0), (3, 0), (4,0), (4,3), (4,4) 이렇게 됩니다.

그 때, 시작점으로 부터 땅 번호로 늘어가면서 BFS_count에는 다리의 길이를 하나씩 쌓습니다.

그러다가, 0이 아니고 자신의 땅 번호와 다른 땅 번호를 만나면, 만나는 땅끼리의 BFS_count를 더하여 결과값을 구했습니다.

위의 예에서는 field가 아래와 같이 됐을 때, 바로 return을 하여 답이 1이 나옵니다.

2 2 2 3 3

2 2 0 0 3

2 0 0 0 0

4 0 0 0 0

4 0 0 5 5

혹시나, 하나의 대륙만 존재할 때를 대비해서 return 0까지 추가했습니다.

100%에서 틀렸습니다 떠서 멘붕먹었습니다..

조언 부탁드립니다...ㅠ

#include <iostream>
#include <queue>
#include <vector>
#include <utility>

#define WHITE 0
#define BLACK 1

using namespace std;

const int dx[4] = { 0,1,0,-1 };
const int dy[4] = { 1,0,-1,0 };

int N;
vector<vector<int>> field; //초기 땅과 바다
vector<vector<int>> color; //BFS 시작점 보관 큐 채우기 위한 COLOR
queue<pair<int, int>> store; //BFS 시작점 보관 큐
vector<vector<int>> BFS_count; //다리 길이를 세기위한 VECTOR

bool isIn(int x, int y)
{
	if (0 <= x && x < N && 0 <= y && y < N)
		return true;
	else
		return false;
}

void devide_field()
{
	int count = 1;
	int newX, newY;
	queue<pair<int, int>> Queue;
	pair<int, int> newPair;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (field[i][j] == 1)
			{
				Queue.push(make_pair(i, j));
				field[i][j] += count;
				
				while (!Queue.empty())
				{
					newPair = Queue.front();
					Queue.pop();

					for (int k = 0; k < 4; k++)
					{
						newX = newPair.first + dx[k];
						newY = newPair.second + dy[k];

						if(isIn(newX,newY))
							if (field[newX][newY] == 1)
							{
								field[newX][newY] += count;
								Queue.push(make_pair(newX, newY));
							}
							else if (field[newX][newY] == 0 && color[newPair.first][newPair.second] == WHITE) // 4방향중에 0이 있는데 이 땅을 아직 store에 안넣었으면
							{
								store.push(newPair);
								color[newPair.first][newPair.second] = BLACK;
							}
					}
				}

				count++;
			}
}

int BFS()
{
	int newX, newY;
	pair<int, int> newPair;

	while (!store.empty())
	{
		newPair = store.front();
		store.pop();

		for (int i = 0; i < 4; i++)
		{
			newX = newPair.first + dx[i];
			newY = newPair.second + dy[i];

			if (isIn(newX, newY))
			{
				if (field[newX][newY] == 0)
				{
					field[newX][newY] = field[newPair.first][newPair.second];
					store.push(make_pair(newX, newY));
					BFS_count[newX][newY] = BFS_count[newPair.first][newPair.second] + 1;
				}
				else if (field[newX][newY] != field[newPair.first][newPair.second])
					return BFS_count[newPair.first][newPair.second] + BFS_count[newX][newY];
			}
		}
	}

	return 0;

}

int main()
{
	vector<int> newLine;
	vector<int> cLine;
	int temp;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		newLine.clear();
		cLine.clear();
		for (int j = 0; j < N; j++)
		{
			cin >> temp;
			newLine.push_back(temp);
			cLine.push_back(WHITE);
		}
		field.push_back(newLine);
		color.push_back(cLine);
		BFS_count.push_back(cLine);
	}

	devide_field();

	cout << BFS() << endl;

	return 0;
}

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

문제

문제

출처

ICPC

2146번 C++ 코드 100%에서 틀렸다고 뜹니다. 반례좀 알려주세요..ㅠㅠ

mycool0905 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말