[BOJ]14226번: 이모티콘 (c++)

https://www.acmicpc.net/problem/14226

14226번: 이모티콘

 

방법 1: 연산 파트를 함수로 처리

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX = 1000;
int time[MAX + 1][MAX + 1];

void check(queue<pair<int, int>> &q, int S, int next, int next_clip, int now)
{
	// 범위를 벗어나거나, 이미 값이 존재하는 경우 종료
	if (next < 0 || next > S || time[next][next_clip] != 0)
	{
		return;
	}
	// 연산횟수 + 1
	time[next][next_clip] = now + 1;
	// 큐에 <연산 후 화면문자 개수, 클립보드 문자 개수> push
	q.push(make_pair(next, next_clip));
}

// 너비우선 탐색으로 S에 도착할 때까지 연산횟수를 time 배열에 저장해나간다.
int bfs(int S)
{
	queue<pair<int, int>> q;
	q.push({ 1, 0 });

	while (!q.empty())
	{
		int now = q.front().first;
		int bf_clip = q.front().second;
		q.pop();

		// 화면 문자개수가 S개가 되면 연산횟수 반환 및 종료
		if (now == S)
		{
			return time[now][bf_clip];
		}

		/*
			복사     : <현재 화면문자       , 현재 화면문자>
			붙여넣기 : <현재 화면문자 + 클립, 클립>
			삭제     : <현재 화면문자 -1    , 클립>
		*/
		check(q, S, now          , now    , time[now][bf_clip]);
		check(q, S, now + bf_clip, bf_clip, time[now][bf_clip]);
		check(q, S, now - 1      , bf_clip, time[now][bf_clip]);
	}

	return S + 1;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int S;
	cin >> S;
	cout << bfs(S);

	return 0;
}

 

방법 2: 연산파트를 반복문으로 처리

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX = 1000;
int time[MAX + 1][MAX + 1];

// 너비우선 탐색으로 S에 도착할 때까지 연산횟수를 저장해나간다.
int bfs(int S)
{
	// <화면 문자개수, 클립보드 문자개수> 를 저장할 큐
	queue<pair<int, int>> q;
	// 1부터 클립보드가 비어있는 채로 연산을 시작한다.
	q.push({1, 0});

	while (!q.empty())
	{
		int now = q.front().first;
		int clip = q.front().second;
		q.pop();

		// 화면 문자개수가 S개가 되면 연산횟수 반환 및 종료
		if (now == S)
		{
			return time[now][clip];
		}
		
		/*
			복사     : <현재 화면문자       , 현재 화면문자>
			붙여넣기 : <현재 화면문자 + 클립, 클립>
			삭제     : <현재 화면문자 -1    , 클립>
		*/
		int next[] = {now, now + clip, now - 1};
		int next_clip[] = {now, clip, clip};

		for (int i = 0; i < 3; ++i)
		{
			// 범위를 넘어났을 때
			if (next[i] < 0 || next[i] >  S)
			{
				continue;
			}
			// 이미 값이 존재할 때 : 이 경우에는 전에 있는 값이 현재 연산횟수 + 1 보다 작다.
			if (time[next[i]][next_clip[i]])
			{
				continue;
			}

			// 큐에 <연산 후 화면문자 개수, 클립보드 문자 개수> push
			q.push({next[i], next_clip[i]});
			// 연산횟수 + 1
			time[next[i]][next_clip[i]] = time[now][clip] + 1;
		}
	}

	return S + 1;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int S;
	cin >> S;
	cout << bfs(S);

	return 0;
}

 

 

방법 1, 2 모두 연산을 수행하는 횟수는 같은데

다른 블로그에서 방법 2처럼 하는걸 처음 봤다. 

신기해서 나도 써봄..

 

 

이 문제는 복사, 붙여넣기, 삭제 3가지의 동작만 할 수 있다.

그리고 다루어야할 변수가 2개 있다.

바로 <현재 화면 문자길이와 클립보드에 저장된 문자 길이>이다. 

S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

최솟값을 구하라고 했으므로, BFS로 풀기로 결정한다.

 

 

그런데 유의할 점이 있다.

클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 

단순히 큐에 문자 길이만을 전달 한다면, 달라진 클립보드의 값은 추적할 수 없다.

그리고 현재 시점에서 선택지가 3개 있음을 잊어서는 안된다. 

이전의 클립보드 내용을 이용해서 붙여넣기만 할수도 있고, 지금 문자내용을 복사할 수도 있다.

 

즉, 큐에 전달해야 할 정보는 <화면 문자길이와 클립보드의 문자길이> 2개이다. 

// 큐에 <연산 후 화면문자 개수, 클립보드 문자 개수> push
q.push(make_pair(next, next_clip));

//이렇게 연산 동작에 따라 
//전달해야할 다음 화면 문자개수와 클립보드 문자개수가 달라진다.

/*
    복사     : <현재 화면문자       , 현재 화면문자>
    붙여넣기 : <현재 화면문자 + 클립, 클립>
    삭제     : <현재 화면문자 -1    , 클립>
*/
check(q, S, now          , now    , time[now][bf_clip]);
check(q, S, now + bf_clip, bf_clip, time[now][bf_clip]);
check(q, S, now - 1      , bf_clip, time[now][bf_clip]);

 

 

그리고 마지막으로! 연산 횟수를 저장할 배열을 선언해준다.

현재 문자길이와 클립보드 문자길이에 따라 연산 횟수가 달라지므로 2차원 배열이 될 것이다.

const int MAX = 1000;
int time[MAX + 1][MAX + 1];

...

// 연산횟수 + 1
time[next][next_clip] = now + 1;

 

 

bfs() 함수 내에서 문자길이가 목표값 S에 도착하면

저장된 연산횟수 = 최소거리를 반환한다.

// 화면 문자개수가 S개가 되면 연산횟수 반환 및 종료
if (now == S)
{
    return time[now][bf_clip];
}