글 읽기 - 예제5번이 틀림니다.

karlema 4년 전 0

예제 5번이 계속 틀리는데 4번다시 설계해서 다시 프로그램 짰는데 왜 맞지 않는지 모르겠습니다. 제가 무언가 고려하지 않고 설계하는 부분이 있는것같은데 혹시 알려주실수 있을까요? 소스 첨부합니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <math.h>
using namespace std;
int n, l, r;
int save[2501];
int map[60][60];
int visit[60][60];
int tempmap[60][60];
int dy[4] = {0,0,1,-1};
int dx[4] = {1,-1,0,0};
int cal = 1;
int mapval = 0;
int result = 0;
void visitinit()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			visit[i][j]=0;
		}
	}
}
void print()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
int bfs(int y,int x,int cnt)
{

	queue<pair<int, int>>q;
	q.push(make_pair(y, x));
	mapval = tempmap[y][x];
	visit[y][x] = cnt;
	cal = 1;
	while (!q.empty())
	{
		int qsize = q.size();
		for (int i = 0; i < qsize; i++)
		{
			int cy = q.front().first;
			int cx = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++)
			{
				int ny = dy[i] + cy;
				int nx = dx[i] + cx;

				if (ny < 0 || nx < 0 || ny >= n || nx >= n || visit[ny][nx]!=0) continue;
				int differ = abs(tempmap[ny][nx] - tempmap[cy][cx]);

				if (differ >= l && differ <= r)
				{
					printf("왔냐\n");
					mapval+= tempmap[ny][nx];
					visit[ny][nx] = cnt;
					cal++;
					
					q.push(make_pair(ny, nx));

				}
			}
		}
	}
	printf("cal %d\n",cal);
	return cal;
}

void backup()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			tempmap[i][j]= map[i][j];
		}
	}
}

void calcul(int cnt)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if(visit[i][j]==cnt)
			map[i][j] = mapval/cal;
		}
	}
}


int main()
{
	scanf("%d %d %d",&n,&l,&r);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			scanf("%d",&map[i][j]);
		}
	}

	while (1)
	{
		int flag = 0;
		int cnt = 0;
		visitinit();
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				backup();
				if (visit[i][j] == 0)
				{
					cnt = cnt + 1;
					if (bfs(i, j, cnt) > 1)
					{
						flag = 1;
						calcul(cnt);
						result++;
						print();
					}
					
				}
			}
		}
		
		if (flag == 0) break;
	}
	printf("%d",result);
	return 0;
}

wjsqjawns 4년 전 1

일단, 해당 문제에서의 인구 이동의 완료는 '모든 국가의 국경이 열린 뒤, 모든 인구의 이동이 완료되고 국경을 다시 닫는 것'을 의미합니다.

따라서, result의 값을 갱신하는 것을, flag 체크를 하는 곳(140번째 line)의 뒤에 두는 게 맞는 것 같아요.

이렇게 수정할 경우, 예제 5번의 결과는 제대로 출력됩니다만, 시간 초과가 발생할 거에요.

karlema 4년 전 1

감사합니다 시간초과만 남았네요... 시간초과가 제일 난감하긴 하지만 설계방법을 알았습니다. 감사합니다.

wjsqjawns 4년 전 1

backup이나 calcul에서의 필요 없는 방문 혹은 연산을 줄이셔야 할 것 같아요.

karlema 4년 전 1

해결했습니다 감사합니다.!!

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

문제

문제

출처

ICPC

예제5번이 틀림니다.

karlema 4년 전 0

wjsqjawns 4년 전 1

karlema 4년 전 1

wjsqjawns 4년 전 1

karlema 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말