글 읽기 - 중복처리

so6275 5년 전 0

이 문제 중복은 어떻게 처리해줘야되나요...

저는 문자가 A,B,C 세개밖에 없으니깐 4진수로 생각해서 이를 A =1, B = 2, C = 3으로 string값을 4진수로 치환해서 풀려고했는데

그러면 최대10개까지 원판이있을수 있어서 4^10 * 4^10 *3(AB,AC,BC) 인데 이렇게만 해도 메모리 초과나버리니깐 방법을 모르겠네요 ㅠ

중복을 어떻게 처리하면 좋을까요? ㅠㅠ

jh05013 5년 전 0

무엇이 중복되나요?

so6275 5년 전 0

예를 들어서

A스틱에 AA

B스틱에 A

C스틱에 A

초기에 이런식으로 되어있을때

A스틱에 가장 위에있는 디스크를 B로 옮기면

A스틱 : A

B스틱 : AA

C스틱 :A

이렇게 되는데

여기서 B스틱에 가장 위에있는 디스크를 A로 옮기면

A스틱 : AA

B스틱 : A

C스틱 : A

이렇게 되는데 이 상태는 초기조건이랑 똑같은 상황이니깐 더 탐색하지 않기위해 막으려고하는데 이때 중복처리를 어떻게하면 좋을지 모르겠어서요..

위 방법이 안되서 A스틱 B스틱 C스틱을 전부 합친다음에 하나의 문자열로 만들어주고 A스틱의 사이즈 B스틱의 사이즈와 같이 저장한다음에

중복처리하려고 했는데, 이방법은 케이스가 많이쌓이게 되면 시간초과가 나버리네요 .. ㅠ

jh05013 5년 전 0

이것만으로는 무슨 상황인지 모르겠습니다. 일단 BFS는 구현하셨나요? "A스틱 B스틱 C스틱을 전부 합친다음에 하나의 문자열로 만들어주고 A스틱의 사이즈 B스틱의 사이즈와 같이 저장"이 바로 중복 처리이고, 이 방법으로 풀 수 있습니다.

so6275 5년 전 0

아래 소스코드처럼 BFS돌리면서 옮길 수 있으면 전부 다 옮기는 식으로 진행했습니다

소스코드 제출결과 시간초과로 나오는데, 새로운 문자열을 만들때마다 중복체크를 다 해줘야되기때문에 이 부분에서 시간초과가 나는거같은데 이 외에 방법을 모르겠습니다 ㅠ

#include <iostream>
#include <queue>
#include <string>
#include <math.h>
using namespace std;

string visit[59049];	// 3^10까지 존재, 사실 A와 B의 length에 따라서 더 존재함 
int visiting[59049][2];
string A_ary = "";
string B_ary = "";
string C_ary = "";
int min_cnt = -1;
int visit_idx = 0;

struct hanoi {
	string A;
	string B;
	string C;
	int cnt;
	hanoi(string a, string b, string c, int d) :A(a), B(b), C(c), cnt(d) {}
};

void bfs();
bool checking(string A, string B, string C);
bool isit_check(string A, int len_A, int len_B);

int main()
{
	int num;

	cin >> num;
	if (num != 0) cin >> A_ary;
	cin >> num;
	if (num != 0) cin >> B_ary;
	cin >> num;
	if (num != 0) cin >> C_ary;

	bfs();
	cout << min_cnt;
	return 0;
}

void bfs()
{
	string sum_s;
	string new_A;
	string new_B;
	string new_C;
	queue<hanoi>q;
	q.push(hanoi(A_ary, B_ary, C_ary, 0));
	visit[visit_idx] = A_ary + B_ary + C_ary;
	visiting[visit_idx][0] = A_ary.size();
	visiting[visit_idx++][1] = B_ary.size();

	while (!q.empty())
	{
		hanoi cur = q.front();
		q.pop();

		if (checking(cur.A, cur.B, cur.C))
		{
			min_cnt = cur.cnt;
			break;
		}

		if (cur.A.size() > 0)
		{
			new_B = cur.B + cur.A[cur.A.size() - 1];
			new_C = cur.C;
			new_A = cur.A.substr(0, cur.A.size() - 1);

			sum_s = new_A + new_B + new_C;
			if (!isit_check(sum_s, new_A.size(), new_B.size()))
			{
				visit[visit_idx] = sum_s;
				visiting[visit_idx][0] = new_A.size();
				visiting[visit_idx++][1] = new_B.size();
				q.push(hanoi(new_A, new_B, new_C, cur.cnt + 1));
			}

			new_B = cur.B;
			new_C = cur.C + cur.A[cur.A.size() - 1];
			new_A = cur.A.substr(0, cur.A.size() - 1);

			sum_s = new_A + new_B + new_C;
			if (!isit_check(sum_s, new_A.size(), new_B.size()))
			{
				visit[visit_idx] = sum_s;
				visiting[visit_idx][0] = new_A.size();
				visiting[visit_idx++][1] = new_B.size();
				q.push(hanoi(new_A, new_B, new_C, cur.cnt + 1));
			}
		}
		if (cur.B.size() > 0)
		{
			new_A = cur.A + cur.B[cur.B.size() - 1];
			new_C = cur.C;
			new_B = cur.B.substr(0, cur.B.size() - 1);

			sum_s = new_A + new_B + new_C;
			if (!isit_check(sum_s, new_A.size(), new_B.size()))
			{
				visit[visit_idx] = sum_s;
				visiting[visit_idx][0] = new_A.size();
				visiting[visit_idx++][1] = new_B.size();
				q.push(hanoi(new_A, new_B, new_C, cur.cnt + 1));
			}

			new_A = cur.A;
			new_C = cur.C + cur.B[cur.B.size() - 1];
			new_B = cur.B.substr(0, cur.B.size() - 1);

			sum_s = new_A + new_B + new_C;
			if (!isit_check(sum_s, new_A.size(), new_B.size()))
			{
				visit[visit_idx] = sum_s;
				visiting[visit_idx][0] = new_A.size();
				visiting[visit_idx++][1] = new_B.size();
				q.push(hanoi(new_A, new_B, new_C, cur.cnt + 1));
			}
		}
		if (cur.C.size() > 0)
		{
			new_A = cur.A;
			new_B = cur.B + cur.C[cur.C.size() - 1];
			new_C = cur.C.substr(0, cur.C.size() - 1);

			sum_s = new_A + new_B + new_C;
			if (!isit_check(sum_s, new_A.size(), new_B.size()))
			{
				visit[visit_idx] = sum_s;
				visiting[visit_idx][0] = new_A.size();
				visiting[visit_idx++][1] = new_B.size();
				q.push(hanoi(new_A, new_B, new_C, cur.cnt + 1));
			}

			new_A = cur.A + cur.C[cur.C.size() - 1];
			new_B = cur.B;
			new_C = cur.C.substr(0, cur.C.size() - 1);

			sum_s = new_A + new_B + new_C;
			if (!isit_check(sum_s, new_A.size(), new_B.size()))
			{
				visit[visit_idx] = sum_s;
				visiting[visit_idx][0] = new_A.size();
				visiting[visit_idx++][1] = new_B.size();
				q.push(hanoi(new_A, new_B, new_C, cur.cnt + 1));
			}
		}
	}
}

bool checking(string A, string B, string C)
{
	int i;
	for (i = 0; i < A.size(); i++) if (A[i] == 'B' || A[i] == 'C') return false;
	for (i = 0; i < B.size(); i++) if (B[i] == 'A' || B[i] == 'C') return false;
	for (i = 0; i < C.size(); i++) if (C[i] == 'A' || C[i] == 'B') return false;

	return true;
}

bool isit_check(string s, int len_A, int len_B)
{
	for (int i = 0; i < visit_idx; i++)
		if (visit[i] == s && len_A == visiting[i][0] && len_B == visiting[i][1]) return true;
	
	return false;
}

jh05013 5년 전 2

중복 체크를 할 때 모든 상태와 일일히 비교하면 안 됩니다. 해싱을 한 다음 배열에 담거나 set, unordered_set 등을 사용하는 식으로 O(1)만에 중복체크를 하도록 만들어 보세요.

so6275 5년 전 0

아.. set을 사용하는 방법이 있었네요 ㅠㅠ

감사합니다 !!

jh05013 5년 전 1

생각해 보니 set은 O(logN)이지만 시간 안에 돌아가는 건 가능할 것 같습니다.

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

문제

문제

출처

ICPC

중복처리

so6275 5년 전 0

jh05013 5년 전 0

so6275 5년 전 0

jh05013 5년 전 0

so6275 5년 전 0

jh05013 5년 전 2

so6275 5년 전 0

jh05013 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말