글 읽기 - 테스트는 도는데, 나머지 케이스에서 무한루프 도는...

jinuu1208 6년 전 0

퍼즐 문제입니다..

BFS 기반으로 풀려고 했고, SHIFT라는 함수를 따로 만들어서, 빈 칸이 상하좌우로 이동하도록 만들었습니다..

테스트 케이스나 간단한 예제(횟수가 5이하인?)에서는 제대로 도는데

나머지 반례에서 무한루프가 도네요..

고수님들 부탁드립니다..

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> shift(vector<int> &a, int flag) // flag : 상하좌우
{
	vector<int> out;
	out = a;

	// 0위치 찾기
	int cur;
	for (int i = 0; i < 9; i++)
	{
		if (a[i] == 0) {
			cur = i; break;
		}
	}
	
	int tmp;	
	//cout << flag<< ' '<< cur << '\n';
	if (flag == 0)// 상
	{
		if (cur >= 3)
		{			
			tmp=out[cur];
			out[cur] = out[cur-3];
			out[cur - 3] = tmp;			
		}
	}
	else if (flag == 1)// 하
	{
		if (cur <=5)
		{	
			//cout << "flag 1\n";
			tmp = out[cur];
			out[cur] = out[cur + 3];
			out[cur + 3] = tmp;
		}
	}
	else if (flag == 2)// 좌
	{
		if ((cur != 0)&& (cur != 3) && (cur != 6))
		{
			//cout << "flag 2\n";
			tmp = out[cur];
			out[cur] = out[cur -1];
			out[cur -1] = tmp;
		}
	}
	else if (flag == 3)// 우
	{
		if ((cur != 2) && (cur != 5) && (cur != 8))
		{
			//cout << "flag 3\n";
			tmp = out[cur];
			out[cur] = out[cur + 1];
			out[cur + 1] = tmp;
		}
	}
	return out;
}
void print_v(vector<int> v)
{
	for (auto it = v.begin(); it != v.end(); it++)
		cout << (*it) << ' ';
	cout << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	vector<int> a(9);
	int cur;
	for (int i = 0; i < 9; i++)
	{
		cin >> a[i];
		if (a[i] == 0) cur = i;
	}

	queue<vector<int>> q;
	q.push(a);

	// 접근 여부 체크를 위한 변수 c
	map<vector<int>, int> c;
	c[a] = 1;
	//c.insert({ a, 1 });
	
	// 최소 횟수 d
	map<vector<int>, int> d;
	//d.insert({a, 0});
	d[a] = 0;

	vector<int> now, next;
	vector<int> ans = { 1,2,3,4,5,6,7,8,0 };
	while (!q.empty())
	{
		now = q.front();
		q.pop();
		if (now == ans) break;
		// 상
		next = shift(now, 0);
		//cout << c[next] << '\n';
		//print_v(next);		
		if ((c[next] == 0)&&(next!=now))
		{
			q.push(next);
			//c.insert({ next, 1 });
			//d.insert({next, d[now] + 1 });
			c[next] = 1;
			d[next] = d[now] + 1;
			if (next == ans) break;
		}
		// 하
		next = shift(now, 1);
		//print_v(next);
		if ((c[next] == 0) && (next != now))
		{
			q.push(next);
			//c.insert({ next, 1 });
			//d.insert({ next, d[now] + 1 });
			c[next] = 1;
			d[next] = d[now] + 1;
			if (next == ans) break;
		}
		// 좌
		next = shift(now, 2);
		//print_v(next);
		if ((c[next] == 0) && (next != now))
		{
			q.push(next);
			//c.insert({ next, 1 });
			//d.insert({ next, d[now] + 1 });
			c[next] = 1;
			d[next] = d[now] + 1;
			if (next == ans) break;
		}
		// 우
		next = shift(now, 3);
		//print_v(next);
		if ((c[next] == 0) && (next != now))
		{
			q.push(next);
			//c.insert({ next, 1 });
			//d.insert({ next, d[now] + 1 });
			c[next] = 1;
			d[next] = d[now] + 1;
			if (next == ans) break;
		}
		//cout << c.size() << '\n';
	}
		

	if (d.count(ans) == 0)
		cout << -1 << '\n';
	else
		cout << d[ans] << '\n';


	//system("pause");
	return 0;

}

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

문제

문제

출처

ICPC

테스트는 도는데, 나머지 케이스에서 무한루프 도는...

jinuu1208 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말