글 읽기 - 메모리가 22MB로 나오는데..

sylim123 5년 전 0

큐에 들어가는 자료형태가 pair<int, pair<pair<int, int>, pair<int, int>>> 인트, (인트쌍, 인트쌍) 이런 구조로 들어가서

비정상적으로 높은걸까요?? 채점 현황 보면 2MB 넘는 분들을 보기가 힘드네요 ㅠㅠ..

#include <stdio.h>
#include <queue>
#include <utility>

using namespace std;

int N, M;
char a[12][12];
// 상 하 좌 우 
// 0 1 2 3

int nextRCase(int x, int y, int dir){
	// 다음 상황을 결정
	// 0: R#  
	// 1: RB#
	// 2: RO
	// 3: RBO
	int i; 
	if(dir == 0){
		// 상 
		bool checkB=false;
		for(i=x+1; i<N; i++){
			if(a[i][y] == '.'){
				continue;
			}else if(a[i][y] == '#'){
				// 처음 맞닥뜨리는 경우 
				if(checkB){
					return 1;
				}else{
					return 0;
				}
			}else if(a[i][y] == 'O'){
				if(checkB){
					return 3;
				}else{
					return 2;
				}
			}else if(a[i][y] == 'B'){
				checkB = true;
				continue;
			}
		}
	}else if(dir == 1){
		// 하 
		bool checkB=false;
		for(i=x-1; i>=0; i--){
			if(a[i][y] == '.'){
				continue;
			}else if(a[i][y] == '#'){
				// 처음 맞닥뜨리는 경우 
				if(checkB){
					return 1;
				}else{
					return 0;
				}
			}else if(a[i][y] == 'O'){
				if(checkB){
					return 3;
				}else{
					return 2;
				}
			}else if(a[i][y] == 'B'){
				checkB = true;
				continue;
			}
		}
	}else if(dir == 2){
		// 좌 
		bool checkB=false;
		for(i=y-1; i>=0; i--){
			if(a[x][i] == '.'){
				continue;
			}else if(a[x][i] == '#'){
				// 처음 맞닥뜨리는 경우 
				if(checkB){
					return 1;
				}else{
					return 0;
				}
			}else if(a[x][i] == 'O'){
				if(checkB){
					return 3;
				}else{
					return 2;
				}
			}else if(a[x][i] == 'B'){
				checkB = true;
				continue;
			}
		}
	}else{
		// 우 
		bool checkB=false;
		for(i=y+1; i<M; i++){
			if(a[x][i] == '.'){
				continue;
			}else if(a[x][i] == '#'){
				// 처음 맞닥뜨리는 경우 
				if(checkB){
					return 1;
				}else{
					return 0;
				}
			}else if(a[x][i] == 'O'){
				if(checkB){
					return 3;
				}else{
					return 2;
				}
			}else if(a[x][i] == 'B'){
				checkB = true;
				continue;
			}
		}
	}
}

int nextBCase(int x, int y, int dir){
	// 다음 상황을 결정
	// 0: B#  
	// 1: BR#
	// 2: BO
	// 3: BRO
	int i; 
	if(dir == 0){
		// 상 
		bool checkR=false;
		for(i=x+1; i<N; i++){
			if(a[i][y] == '.'){
				continue;
			}else if(a[i][y] == '#'){
				// 처음 맞닥뜨리는 경우 
				if(checkR){
					return 1;
				}else{
					return 0;
				}
			}else if(a[i][y] == 'O'){
				if(checkR){
					return 3;
				}else{
					return 2;
				}
			}else if(a[i][y] == 'R'){
				checkR = true;
				continue;
			}
		}
	}else if(dir == 1){
		// 하 
		bool checkR=false;
		for(i=x-1; i>=0; i--){
			if(a[i][y] == '.'){
				continue;
			}else if(a[i][y] == '#'){
				// 처음 맞닥뜨리는 경우 
				if(checkR){
					return 1;
				}else{
					return 0;
				}
			}else if(a[i][y] == 'O'){
				if(checkR){
					return 3;
				}else{
					return 2;
				}
			}else if(a[i][y] == 'R'){
				checkR = true;
				continue;
			}
		}
	}else if(dir == 2){
		// 좌 
		bool checkR=false;
		for(i=y-1; i>=0; i--){
			if(a[x][i] == '.'){
				continue;
			}else if(a[x][i] == '#'){
				// 처음 맞닥뜨리는 경우 
				if(checkR){
					return 1;
				}else{
					return 0;
				}
			}else if(a[x][i] == 'O'){
				if(checkR){
					return 3;
				}else{
					return 2;
				}
			}else if(a[x][i] == 'R'){
				checkR = true;
				continue;
			}
		}
	}else{
		// 우 
		bool checkR=false;
		for(i=y+1; i<M; i++){
			if(a[x][i] == '.'){
				continue;
			}else if(a[x][i] == '#'){
				// 처음 맞닥뜨리는 경우 
				if(checkR){
					return 1;
				}else{
					return 0;
				}
			}else if(a[x][i] == 'O'){
				if(checkR){
					return 3;
				}else{
					return 2;
				}
			}else if(a[x][i] == 'R'){
				checkR = true;
				continue;
			}
		}
	}
}

pair<int, int> nextPos(int x, int y, int dir, int c){
	// 다음 좌표를 알려주는
	// dir 0 1 2 3 위 아래 왼쪽 오른쪽
	// case는 0 혹은 1
	int i;
	if(dir == 0){
		// 위 
		for(i=x+1; i<N; i++){
			if(a[i][y] != '#'){
				continue;
			}
			if(c == 0){
				return make_pair(i-1, y);
			}else{
				return make_pair(i-2, y);
			}
		}
	}else if(dir == 1){
		// 아래 
		for(i=x-1; i>=0; i--){
			if(a[i][y] != '#'){
				continue;
			}
			if(c == 0){
				return make_pair(i+1, y);
			}else{
				return make_pair(i+2, y);
			}
		}
	}else if(dir == 2){
		// 왼쪽 
		for(i=y-1; i>=0; i--){
			if(a[x][i] != '#'){
				continue;
			}
			if(c == 0){
				return make_pair(x, i+1);
			}else{
				return make_pair(x, i+2);
			}
		}
	}else{
		// 오른쪽 
		for(i=y+1; i<M; i++){
			if(a[x][i] != '#'){
				continue;
			}
			if(c == 0){
				return make_pair(x, i-1);
			}else{
				return make_pair(x, i-2);
			}
		}
	}
}

int bfs(pair<int, int> R, pair<int, int> B){
	/* 
		오른쪽으로 갈 경우 
		1. nextR 3아니면 가능 && nextB 0, 1일때 가능 
		2. nextR 2면 종료 nextR 2 아니면 좌표 받기
		3. 큐에 좌표 저장 
	*/
	// 큐 input pair<count, pair<pair, pair>>
	queue <pair<int, pair<pair<int, int>, pair<int, int> > > > q;
	q.push(make_pair(0, make_pair(R, B)));
	while(!q.empty()){
		int count = q.front().first;
		int currentRX, currentRY, currentBX, currentBY;
		currentRX = q.front().second.first.first;
		currentRY = q.front().second.first.second;
		currentBX = q.front().second.second.first;
		currentBY = q.front().second.second.second;
		a[currentRX][currentRY] = 'R';
		a[currentBX][currentBY] = 'B';
		q.pop();
		if(count == 10){
			// 아직 안만듬 
			return -1;
		}
		for(int i=0; i<4; i++){
			int nextRC, nextBC;
			nextRC = nextRCase(currentRX, currentRY, i);
			nextBC = nextBCase(currentBX, currentBY, i);
			if(nextRC!=3 && (nextBC==0||nextBC==1)){
				if(nextRC == 2){
					return (count + 1);
				}else{
					pair<int, int> nextR, nextB;
					nextR = nextPos(currentRX, currentRY, i, nextRC);
					nextB = nextPos(currentBX, currentBY, i, nextBC);
					q.push(make_pair(count+1, make_pair(nextR, nextB)));
				}
			} 
		}
		a[currentRX][currentRY] = '.';
		a[currentBX][currentBY] = '.';
	}
}

int main(void){
	int i, j;
	pair<int, int> posR, posB;
	scanf("%d %d", &N, &M);
	for(i=0; i<N; i++){
		scanf("%s", a[i]);
	}
	for(i=0; i<N; i++){
		for(j=0; j<M; j++){
			if(a[i][j] == 'R'){
				posR = make_pair(i, j);
			}else if(a[i][j] == 'B'){
				posB = make_pair(i, j);
			}else{
				continue;
			}
		}
	}
	printf("%d\n", bfs(posR, posB));
	
	return 0;
}

gomyk12 5년 전 1

bfs로 뻗어나가면서 차지한 메모리가 큰 것 같습니다. 가지치기를 할 수 있는 방법을 고민해보시면 좋을 것 같습니다

gomyk12 5년 전 1

그리고, bfs는 넓이 우선으로 탐색하다보니 dfs에 비해 더 많은 메모리를 사용 할 수 밖에 없습니다.

sylim123 5년 전 0

조언 감사드립니당!

startlink 5년 전 0

DP로 풀면 됩니다.

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

문제

문제

출처

ICPC

메모리가 22MB로 나오는데..

sylim123 5년 전 0

gomyk12 5년 전 1

gomyk12 5년 전 1

sylim123 5년 전 0

startlink 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말