글 읽기 - 교환(BFS) 조언 부탁드립니다!

DryType 7년 전 0

전형적인 bfs로 풀었습니다.

visit배열은 K연산을 한번 수행할 때 마다 초기화 시켜서 모든 경우가 고려되도록 하였습니다.

바로 WA가 뜨는걸 보면 뭔가 실수한것 같습니다. 이 문제 정답률 더 떨어지겠네요 저때문에 ㅠㅠ

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

bool visit[1000001];

int main()
{
	queue<int> q;
	int N, M, K, m, q_sz, tmp, maxNum;
	scanf("%d %d", &N, &K);

	//몇자리 수인지 구하기
	m = 1;
	M = 10;
	while (M<=N)
	{
		M *= 10;
		m++;
	}
	q.push(N);
    
	//-1인 경우 처리
	if (m == 1)
	{
		if (K > 0) printf("-1\n");	
		else printf("%d\n", N);
		return 0;
	}
	else if (m == 2 && N%10 == 0)
	{
		if (K > 0)	printf("-1\n");
		else printf("%d\n",N);
		return 0;
	}

	int d[8] = { 0, }, a, b;
	while (K--)
	{
		q_sz = q.size();
		memset(visit, 0, sizeof(visit));
		for (int qc = 0; qc < q_sz; qc++)
		{			
			tmp = q.front();
			q.pop();
			a = 1;
			//1~m자리수 까지 배열의 해당 인덱스에 넣음
			while (tmp>0)
			{
				d[a++] = tmp % 10;
				tmp /= 10;
			}

			for (int i = 1; i < m; i++)
			{
				for (int j = i + 1; j <= m; j++)
				{
					//첫번째 자리수와 0이 교환하는 경우 넘김
					if (j == m && d[i] == 0) continue;
					tmp = 0;
					b = 1;
					swap(d[i], d[j]);
					for (int k = 1; k <= m; k++)
					{
						tmp += d[k] * b;
						b *= 10;
					}
					if (!visit[tmp])
					{
						visit[tmp] = 1;
						q.push(tmp);
					}
					swap(d[i], d[j]);
				}
			}
		}
	}

	while (!q.empty())
	{
		maxNum = max(maxNum, q.front());
		q.pop();
	}	
	printf("%d\n", maxNum);
	return 0;
}

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

문제

문제

출처

ICPC

교환(BFS) 조언 부탁드립니다!

DryType 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말