글 읽기 - 틀린 이유? 반례가 필요해요 .. ㅠㅠ (인구 이동 문제)

ekfrhkquf12 4년 전 0

인구 이동 문제입니다. 예제는 다 맞게 나와요 ㅠㅠ

채점 거의 끝까지 가는데 맨 마지막 케이스에서 틀리는 것 같습니다.

어디서 틀린 걸까요?

main에 있는 while문은 기본적으로 한번 돌 때마다

장벽 이동을 할 수 있는 모든 도시들의 위치 정보가 저장된 vector의 vector를 생성한 후에 update를 한번에 진행합니다.

후에 다시 while문들 돌면서 bfs를 수행합니다...!!

뭐가 문제일까요.. ㅠㅠ

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<vector>
#include<queue>
#include<math.h>
#include<string.h>

using namespace std;
int** matrix;
bool** visited;
int n, l, r;
//오른쪽 왼쪽 위 아래 
int dy[] = { 0,0, -1, 1 };
int dx[] = { 1,-1,0,0 };
int bfs();
void update();
void out();
queue<pair<int, int> > myqueue;
vector<vector<pair<int, int> > > locations;

int main() {
	//반복이 생성을 만든다.
	cin >> n >> l >> r;
	visited = (bool**)malloc(n * sizeof(bool*));
	matrix = (int**)malloc(n * sizeof(int*));
	for (int i = 0; i < n; i++) {
		matrix[i] = (int*)malloc(sizeof(int)*n);
		visited[i] = (bool*)malloc(sizeof(bool)*n);
		for (int j = 0; j < n; j++) 
			cin >> matrix[i][j];
	}
	
	//out();
	//시간제한 2초임.. bfs로 해야 하나? 
	//visited이면 skip하기
	//방문 체크를 어떻게 해야 할까?
	bool flag = false;
	int count = 0;

	while (flag!=true) {
		for (int i = 0; i < n; i++)
			fill(visited[i], visited[i]+n, false);
			//for (int j = 0; j < n; j++)
				//memset(visited[i], false, sizeof(visited[i]));
				//visited[i][j] = false;
		
		for (int i = 0; i < n; i++) {
			if (flag == true) break;
			for (int j = 0; j < n; j++) {
				myqueue.push(make_pair(i, j));
				if (bfs() == 1)
					flag = true;
				/*switch (bfs()) {
				case 0:
					count++;
					update();
					break;
				case 1:
					count++;
					update();
					flag = true;
					break;
				case 2: 
					break;
					
				}*/
			}
		}

		if (locations.size() == 0) // 인구인동을 못하는 상황
			break;
		if (flag == true) { //인구이동이 더이상 필요 없는 상황
			count++;
			update();
			break;
		}

		else {
			count++;
			update();
		}


		//out();
	}

	printf("%d", count);
	return 0;
	
}


int bfs() {
	visited[myqueue.front().first][myqueue.front().second] = true;
	vector<pair<int, int> > temp_locations;
	int temp_sum = 0;
	int count = 0;

	while (!myqueue.empty()) {
		pair<int, int> temp = myqueue.front();
		int y = temp.first;
		int x = temp.second;

		temp_locations.push_back(temp);
		temp_sum += matrix[y][x];
		count++;

		myqueue.pop();
		for (int i = 0; i < 4; i++) {
			int temp_y = y + dy[i];
			int temp_x = x + dx[i];

			if (temp_y >= n || temp_y < 0 || temp_x >= n || temp_x < 0)
				continue;
			if (visited[temp_y][temp_x])
				continue;
			if (abs(matrix[y][x] - matrix[temp_y][temp_x]) > r || abs(matrix[y][x] - matrix[temp_y][temp_x]) < l)
				continue;

			visited[temp_y][temp_x] = true;
			myqueue.push(make_pair(temp_y, temp_x));
		}
	}
	temp_locations.push_back(make_pair(temp_sum, count));

	
	if (temp_locations.size() == n * n + 1) {
		locations.push_back(temp_locations);
		return 1;
	}
	else if (temp_locations.size() != 2) {
		locations.push_back(temp_locations);
		return 0;
	}
	else
		return 2;
}


void update() {
	while (!locations.empty()) {
		vector<pair<int, int> > temp_locations = locations.back();
		locations.pop_back();
		pair<int, int> data = temp_locations.back();
		temp_locations.pop_back(); 
		int buffer = data.first / data.second;
		for (int i = 0; i < temp_locations.size(); i++) {
			int y = temp_locations.at(i).first;
			int x = temp_locations.at(i).second;
			matrix[y][x] = buffer;
		}
	}
}

void out() {

	for (int i = 0; i < n; i++) {
		cout << '\n';
		for (int j = 0; j < n; j++)
			cout << matrix[i][j] << ' ';
	}

}

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

문제

문제

출처

ICPC

틀린 이유? 반례가 필요해요 .. ㅠㅠ (인구 이동 문제)

ekfrhkquf12 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말