글 읽기 - 79% 시간초과 질문 드립니다.

atree1639 4년 전 0

79% 에서 시간초과가 계속 걸리는 중입니다.

탈출 조건이 잘 못 된 것으로 생각하여 계속 찾아보는 중입니다. ( 이상 없는 것 같습니다..)

음... 하루가 지났는데도 정말 모르겠네요.

도움을 요청드립니다.

#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;

void in();
void bfs(int x, int y, int areaCnt);
void mapSetting(int areaCnt);

#define mMax	51

struct point {
	int x;
	int y;
	int area;
};

int N, L, R;
int map[mMax][mMax];
int unionMap[mMax][mMax];
int visited[mMax][mMax];
int dir[4][2] = { { 1,0 } ,{ -1,0 } ,{ 0,1 } ,{ 0,-1 } };
queue<point> q;

void bfs(int x, int y, int areaCnt) {

	// 지역 함수
	int curX = 0; int curY = 0; int nextX = 0; int nextY = 0; int difNum = 0;

	// 초기화
	while (!q.empty()) q.pop();
	memset(visited, 0x00, sizeof(visited));

	q.push({ x, y, areaCnt });
	unionMap[x][y] = areaCnt;
	visited[x][y] = 1;

	while (!q.empty()) {
		curX = q.front().x;
		curY = q.front().y;
		q.pop();

		for (int i = 0; i < 4; i++) {
			nextX = curX + dir[i][0];	// 세로
			nextY = curY + dir[i][1];	// 가로

			// 통과조건 : 배열 범위에 맞을 경우
			if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
			
			// 통과조건 : 배열에 방문 하지 않았을 경우
			if (visited[nextX][nextY] != 0) continue;
			
			// 두 수의 차이 구하기
			difNum = map[curX][curY] > map[nextX][nextY] ?
							map[curX][curY] - map[nextX][nextY] :
							map[nextX][nextY] - map[curX][curY];

			// 통과 조건 : [ L <= X <= R ]
			if (difNum < L || difNum > R) continue;

			//cout << "(" << nextX << " , " << nextY << " )" << endl;
			unionMap[nextX][nextY] = areaCnt;
			visited[nextX][nextY] = 1;
			q.push({ nextX, nextY, areaCnt });
		}
	}
}

void mapSetting(int areaCnt) {

	// 지역 함수
	int totalNum = 0;
	int totalCnt = 0;

	// 연합 수 만큼 반복문
	for (int i = 1; i <= areaCnt; i++) {
		// i번째 연합 친구들의 인구를 다 더함
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				if (unionMap[j][k] == i) {
					totalNum += map[j][k];
					totalCnt++;
				}
			}
		}

		// i번째 연합 친구들의 평균 인구 수를 구함
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				if (unionMap[j][k] == i) {
					map[j][k] = totalNum / totalCnt;
				}
			}
		}
		totalNum = 0;
		totalCnt = 0;
	}
}

int main() {

	int answer = 0;
	int areaCnt = 0;

	in();

	while (1) {

		// 초기화
		memset(unionMap, 0x00, sizeof(unionMap));

		// 연합 만들기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (unionMap[i][j] == 0) {
					areaCnt++;
					bfs(i, j, areaCnt);
				}
			}
		}


        // 탈출 조건
		if (areaCnt >= N * N) break;
        
        // 인구 이동 + 1
		answer++;
        // 다음 Map 세팅
		mapSetting(areaCnt);
        areaCnt = 0;
	}


	cout << answer << endl;

	return 0;
}

void in() {
	cin >> N >> L >> R;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];
    
}

dowk0331 4년 전 0

76~97 줄의 연합의 평균을 구하는 곳이 살짝 비효율적으로 보입니다.

처음에 bfs를 돌리실 때 totalSum을 계산 해주시고 연합번호를 인덱스로 하는 배열로 저장만 해두면 (연합갯수*N*N)의 탐색을 안해도 되니까요

(이게 큰 영향을 미칠지 아닐지는 모르겠네요.. 지나가다 댓글 한번 달아봅니다)

atree1639 4년 전 0

dowk0331

감사합니다. 말씀해주신 것처럼 bfs를 돌릴때 totalSum을 계산해주고, 연합번호를 인덱스로 하는 배열에 저장하여 탐색을 하는 중복코드를 제거 하였지만....

여전히 78~79% 에서 시간초과로 걸리네요 ㅎㅎ

그래도 답변 감사드립니다.

atree1639 4년 전 2

dowk0331

오.... 드디어 해결하였습니다.

71 - 86 라인을 제거 한 후 - bfs를 돌릴때 totalSum을 계산해주고, 연합번호를 인덱스로 하는 배열에 저장하여 탐색을 하는 중복코드를 제거 하였고

87 - 94 라인을 제거 한 후 최적화 해주니까 바로 통과네요 !

for(for(bfs)) 의 의미를 이제 알겠습니다.

감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

79% 시간초과 질문 드립니다.

atree1639 4년 전 0

dowk0331 4년 전 0

atree1639 4년 전 0

dowk0331

atree1639 4년 전 2

dowk0331

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말