글 읽기 - 버스 갈아타기 메모리 초과 뜹니다.

hj_d 7년 전 0

소스는 아래와 같이 해서 제출 했는데 메모리 초과가 뜨더라구요 ㅜㅜ

그런데 제가 생각 에는 메모리 초과에 왜 뜨는지 도저히 모르겠습니다.

일단 각 버스 노선 끼리 겹치는 구간을 다 찾아서 각각 이동 할수 있는 노선을 다 찾고

BFS 로 찾았는데, 답은 잘 나오는데 메모리 초과가 뜹니다. BFS 할때 메모리 초과 나는건지...

어디에서 나는 건지 알고 싶습니다.

#include<stdio.h>
#include<queue>
#include<vector>
#define MAX(x,y) ( x > y ? x : y)
#define MIN(x,y) ( x < y ? x : y)
using namespace std;
struct bus {
	int col = 0, row = 0;
	int start, end;
};
int main() {
	int m, n, k,i,j,ans=0;
	int num, x1, y1, x2, y2;
	int a, b;
	int d[5001] = { 0 };
	bus table[5001];
	vector <int> g[5001];
	queue <int> que;
	scanf("%d %d %d", &m, &n, &k);
	for (i = 0; i < k; i++)
	{
		scanf("%d %d %d %d %d", &num, &x1, &y1, &x2, &y2);
		if (x1 == x2&&y1 != y2) {
			table[i].row = x1;
			table[i].start = MIN(y1, y2);
			table[i].end = MAX(y1, y2);
		}
		else if (x1 != x2&&y1 == y2) {
			table[i].col = y1;
			table[i].start = MIN(x1, x2);
			table[i].end = MAX(x1, x2);
		}
		for (j = 0; j < i; j++) {
			if (table[i].col) {
				if (table[j].row) {
					if (table[i].start <= table[j].row&&table[j].row <= table[i].end&&table[j].start <= table[i].col&&table[i].col <= table[j].end) {
						g[i].push_back(j);
						g[j].push_back(i);
					}
				}
				else if (table[j].col) {
					if (table[i].col == table[j].col) {
						if (table[i].start <= table[j].start&&table[j].end <= table[i].end) {
							g[i].push_back(j);
							g[j].push_back(i);
						}
						else if (table[j].start <= table[i].start&&table[i].end <= table[j].end) {
							g[i].push_back(j);
							g[j].push_back(i);
						}
						else if (table[i].start <= table[j].start&&table[j].start <= table[i].end) {
							g[i].push_back(j);
							g[j].push_back(i);
						}
						else if (table[i].start <= table[j].end&&table[j].end <= table[i].end) {
							g[i].push_back(j);
							g[j].push_back(i);
						}
					}
				}
			}
			else if(table[i].row) {
				if (table[j].col) {
					if (table[i].start <= table[j].col&&table[j].col <= table[i].end&&table[j].start <= table[i].row&&table[i].row <= table[j].end) {
						g[i].push_back(j);
						g[j].push_back(i);
					}
				}
				else if (table[j].row) {
					if (table[i].row == table[j].row) {
						if (table[i].start <= table[j].start&&table[j].end <= table[i].end) {
							g[i].push_back(j);
							g[j].push_back(i);
						}
						else if (table[j].start <= table[i].start&&table[i].end <= table[j].end) {
							g[i].push_back(j);
							g[j].push_back(i);
						}
						else if (table[i].start <= table[j].start&&table[j].start <= table[i].end) {
							g[i].push_back(j);
							g[j].push_back(i);
						}
						else if (table[i].start <= table[j].end&&table[j].end <= table[i].end) {
							g[i].push_back(j);
							g[j].push_back(i);
						}
					}
				}
			}
		}
	}
	scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
	for (i = 0; i < k; i++) {
		if (table[i].row == x1&&table[i].start<=y1&&y1<=table[i].end) {
			que.push(i);
			d[i] = 1;
		}
		else if (table[i].col == y1&&table[i].start<=x1&&x1<=table[i].end) {
			que.push(i);
			d[i] = 1;
		}
	}

	while (!que.empty()) {
		a = que.front();
		que.pop();
		n = d[a];
		if (table[a].row == x2&&table[a].start <= y2&&y2 <= table[a].end) {
			ans = d[a];
			break;
		}
		else if (table[a].col == y2&&table[a].start <= x2&&x2 <= table[a].end) {
			ans = d[a];
			break;
		}
		for (i = 0; i < g[a].size(); i++) {
			b = g[a][i];
			if (!d[b]) {
				d[b] = n + 1;
				que.push(b);
			}
		}
	}
	printf("%d\n", ans);
}

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

문제

문제

출처

ICPC

버스 갈아타기 메모리 초과 뜹니다.

hj_d 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말