글 읽기 - 메모리 초과인데 왜 메모리가 터졌는지 잘 모르겠습니다.

ploffer11 5년 전 0

6개월 전에 풀었다가 실패한 후, 리벤지하러 왔는데 또 실패했습니다.

처음엔 틀렸습니다가 뜨길래 게시판에서 반례 찾아서 반례를 해결 후 제출했더니 메모리초과를 받습니다.

큐에 push 때문에 메모리 초과가 뜨는 거 같은데, 제가보기엔 아무리 생각해도 큐에 최대 200*200*30, 즉

1,200,000 개 정도밖에 안들어갑니다.

이정도로 메모리 초과가 일어나진 않을텐데, 뭐가 문제인지 모르겠습니다.

코드에 주석 열심히 달아 놓았으니, 조언 부탁드립니다.

#include <iostream>
#include <tuple>
#include <queue>
#include <map>
using namespace std;
typedef tuple<int, int, int, int> t;

bool visit[205][205][32];
bool matrix[205][205];

int r, c, k, x;
int dr[] = { 1, -1, 0, 0, 1, 1, 2, 2, -1, -1, -2, -2 };
int dc[] = { 0, 0, 1, -1, 2, -2, 1, -1, 2, -2, 1, -1 };

bool check(int R, int C, int K)
{
    // 범위에 벗어나는지 체크, 1 based로 문제를 풀었습니다.
	if ( 1 <= R && R <= r && 1 <= C && C <= c )
	{
        // 범위 안이라면, matrix[R][C] (벽이 있으면 true) 이거나
        // visit[R][C][K] (말처럼 K번 움직여서 방문한 적 있으면 true) 인지 확인
        // 하나라도 true라면 거긴 방문할 필요가 없으므로 return false
		if ( matrix[R][C] or visit[R][C][K] ) return false;
        // 아니면 return true
		else return true;
	}
    // 범위에 벗어나면 false 반환
	else return false;
}

int bfs(int goal_r, int goal_c, int max_k)
{
    // 큐는 총 네개를 저장하는 튜플
	queue<t> q;

    // (깊이, 말처럼움직인횟수, 현재좌표 r, 현재좌표 c) 꼴로 저장
	q.push(t(0, 0, 1, 1));
    // 말처럼 0번 움직여 1,1 를 방문했으므로 visit[1][1][0] 는 true
	visit[1][1][0] = true;

	while ( !q.empty() )
	{
        // c++ 17 확장 문법 
		auto[depth, k, r, c] = q.front();
		q.pop();

		if ( r == goal_r && c == goal_c ) return depth;

		for ( int i = 0; i < 12; i++ )
		{
			int R = r + dr[i], C = c + dc[i];
            // 범위체크, visit체크, matrix (벽 유무)체크 전부 check함수가 해줌
			if ( check(R, C, k) )
			{
                // check함수를 통과했는데 i<4일경우는 상하좌우 움직임이므로
                // k를 건들지 않음
				if ( i < 4 )
				{
					if ( R == goal_r && C == goal_c ) return depth + 1;
					visit[R][C][k] = true;
					q.push(t(depth + 1, k, R, C));
				}
                // i<4가 아니라면 i>=4이고, 이 때는 k가 max_k보다 작아야만 큐에 푸시
				else if ( k < max_k )
				{
					if ( R == goal_r && C == goal_c ) return depth + 1;

					visit[R][C][k + 1] = true;
					q.push(t(depth + 1, k + 1, R, C));
				}
			}
		}
	}

    // 큐가 비어서 이 곳으로 올 경우, -1을 리턴 (도달 불가능)
	return -1;
}

int main()
{
	cin >> k >> c >> r;

	for ( int i = 1; i <= r; i++ )
	{
		for ( int j = 1; j <= c; j++ )
		{
			cin >> matrix[i][j];
		}
	}

	cout << bfs(r, c, k);
}

ploffer11 5년 전 1

아.... 허무한 실수였군요.

i < 4와 i >= 4에 서로 다른 check 함수를 적용했어야했는데, 아무 생각 없이 코드를 짰네요.

덕분에 리벤지 성공했습니다.

감사합니다.

sis04013 8달 전 0

저도 완전 똑같은 실수를 해서 메모리가 터졌는데 덕분에 찾았습니다.

감사합니다 :D

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

문제

문제

출처

ICPC

메모리 초과인데 왜 메모리가 터졌는지 잘 모르겠습니다.

ploffer11 5년 전 0

ploffer11 5년 전 1

sis04013 8달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말