글 읽기 - c++ 메모리 초과 문제입니다

dudgns2043 2년 전 0

메모리 초과가 나오는데 이유를 잘 모르겠습니다.

우선 예제에 있는 강물 출력시에 정상적으로 출력이 되고 답도 나옵니다

호수에 백조 2마리 위치를 저장한다음 절대값으로 서로의 위치 차이 만큼 따로 저장 후 dfs 돌렸는데 잘못된 방법인가요?

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

bool meet = false;
void dfs(pair<int, int> p1, pair<int, int> p2, vector<vector<char>> v, vector<vector<bool>> chk){
   	if (p1 == p2) {
		meet = true;
		return;
	}
	chk[p1.first][p1.second] = true;

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

	for (int i = 0; i < 4; i++) {
		
		int x = p1.first + dx[i];
		int y = p1.second + dy[i];

		if ((0 <= x && v.size() > x) && (0 <= y && v[0].size() > y) && !chk[x][y]) {
			if (v[x][y] != 'X') {
				p1.first = x;
				p1.second = y;
				dfs(p1, p2, v, chk);
			}

		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<vector<char>> v(n+1, vector<char>(m+1));

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char c;
			cin >> c;
			v[i][j] = c;
		}
	}

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

	while (1) {
		
		vector<vector<bool>> chk(n + 1, vector<bool>(m+1, false));
		vector<pair<int, int>> p;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (v[i][j] == '.' || v[i][j] == 'L') {
					if (chk[i][j] == true) continue;

					if (v[i][j] == 'L') {
						p.push_back(make_pair(i, j));
					}

					for (int k = 0; k < 4; k++) {
						int x = i+dx[k];
						int y = j+dy[k];

						if ((1<=x && n>=x) && (1<=y && m>=y) && !chk[x][y]) {

							if (v[x][y] == 'X') {
								v[x][y] = '.';
								chk[x][y] = true;
							}
						}
					}
				}
			}
		}

		vector<vector<bool>> ck(n + 1, vector<bool>(m + 1, false));
		
		int lake_x = abs(p[0].first - p[1].first);
		int lake_y = abs(p[0].second - p[1].second);

		int maxX = 0;
		int maxY = 0;

		if (p[0].first < p[1].first) {
			maxX = p[1].first;
		}
		else {
			maxX = p[0].first;
		}
		

		if (p[0].second < p[1].second) {
			maxY = p[1].second;
		}
		else {
			maxY = p[0].second;
		}

		vector<vector<char>> v2(lake_x+1);
		int c = 0;

		for (int i = maxX-lake_x; i <= maxX; i++) {
			for (int j = maxY-lake_y; j <= maxY; j++) {

				v2[c].push_back(v[i][j]);
				
			}
			c++;
		}

		p[0].first = 0;
		p[0].second = 0;

		p[1].first = lake_x;
		p[1].second = lake_y;

		dfs(p[0], p[1],v2,ck);
		cnt++;

		if (meet) {
			cout << cnt<<endl;
			break;
		}
		
		
	}

	return 0;
}

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

문제

문제

출처

ICPC

c++ 메모리 초과 문제입니다

dudgns2043 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말