글 읽기 - 1525번 퍼즐 메모리초과 질문입니다! 헬프미~

xotmd17 5년 전 0

vector에 1 0 3 4 2 5 7 8 6 가 있을 시

0이 있는 위치에서 +1, -1, +3, -3을 이동시키는 부분은 이동할 수 있는 부분이라고 생각했습니다.(단, 범위 내에서)

vector를 이동시키고 visited로 방문한 적이 없는 모양이면 push와 visited를 set했습니다.

메로리 초과라고 해서 vector<int> 를 vector<char>로 했는데 다른 문제가 있는것 같습니다.

코드의 자세한 내용은 주석처리 했습니다.

도와주세요 헬프미~

#include<iostream>
#include<vector>
#include<set>
#include<queue>
using namespace std;

#define swap(x, y) do{int t; t=x; x=y; y=t;}while(0) //swap 매크로 함수

vector<char> Puzzle; // 1 2 3 4 5 6 7 8 0 을 저장할 vector

bool correct(vector<char> t) //t와 Puzzle이 같은 모양이라면 1을 리턴 아니라면 0을 리턴
{
	for(int i=0; i<9; i++)
	{
		if(t[i] != Puzzle[i])
			return 0;
	}
	return 1;
}

int BFS(vector<char> First)
{
	int m[4] = {-1, 1, -3, 3}; //이동 방향
	int count = 1;
	queue<vector<char>> que;
	set<vector<char>> visited; //방문을 check하는 set

	que.push(First);
	visited.insert(First);

	while(!que.empty())
	{
		int Nque = que.size(); 
		for(int n = 0; n < Nque; n++) //que의 사이즈만큼 전부 돌린 후 count++을 한다.
		{
			vector<char> now = que.front(); //que에서 뽑아낸 모양을 now에 저장
			que.pop();
			int zero = 0; //0이 있는 위치를 저장할 변수
			for(;now[zero]!=0;zero++); //0의 위치를 찾아내는 for문
			for(int i=0; i<4; i++) //4개의 움직임을 위한 for문
			{
				int mv = zero + m[i];
				if(mv > -1 && mv < 10) //움질일 범위를 체크
				{
					vector<char> next = now; //다음 모양을 저장할 next
					swap(next[mv], next[zero]);
					if(correct(next)) //만약 Puzzle의 모양과 일치한다면 실행
						return count;
					if(visited.find(next) == visited.end()) //방문한 적이 없다면 실행
					{
						que.push(next);
						visited.insert(next);
					}
				}
			}
		}
		count++; //한 큐의 내용을 전부 수행했다면 count++
	}
	return -1; //모든 큐를 돌았지만 값이 없다면 -1
}

int main(void)
{
	vector<char> P;
	
	for(int i=1; i<10; i++)
	{
		int n;
		cin >> n;
		P.push_back(n);
		Puzzle.push_back(i);
	}
	Puzzle[8] = 0;
	
	if(correct(P)) //처음부터 같은 모양이라면 0을 출력
	{
		cout << 0 << endl;
		return 0;
	}
	cout << BFS(P) << endl;
}

jh05013 5년 전 1

이 문제의 메모리 제한은 16MB입니다. set<vector<char>>나 queue<vector<char>>보다 메모리를 아끼는 방법을 생각해 보세요.

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

문제

문제

출처

ICPC

1525번 퍼즐 메모리초과 질문입니다! 헬프미~

xotmd17 5년 전 0

jh05013 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말