JUNGOL/Intermediate_Coder/그래프탐색-BFS/1336 : 소수 함께 하는 여행

Intermediate_Coder/그래프탐색-BFS/소수와 함께 하는 여행

---

문제                                            

 뉴욕으로 날아간 원더걸스를 찾기 위해서 태현이도 뉴욕에 가게 되었다.
 뉴욕에 도착하여 입국  마친 태현이는 막상 도착하고 보니 아무것도 할 수 없었다.
 다행스럽게 공항에 있는 사람들에게 손짓 발짓으로 버스를 타는 방법을 알게 되었다.
 
 뉴욕의 정류장은 각각 번호가 붙어 있는데, 이는 네 자리의 소수로 이루어져 있다.
 한 정류장의 번호와, 다른 정류장의 번호의 각 자리들을 비교 했을 때, 자리가 하나만 다른 경우는 이동하는 버스가 존재 하므로 이동이 가능하다.
 가령 '1033'번 정류장과 '1733'번 정류장의 경우 차이 나는 경우가 1개 밖에 없기 때문에 버스가 존재 하므로 이동이 가능하나,
 '1033'번에서 '3733'번의 경우에는 차이가 2개 이상 나기 때문에 버스가 존재하지 않는다.
 한 정류장에서 다른 정류장으로 이동 할 때는 반드시 버스를 타야하고, 요금을 내야 한다.
 
 태현이가 지금 '1033'번 정류장에서 '8179' 정류장으로 이동하기 위해서 거쳐야하는 정류장은 다음과 같다.
 
 1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179
 
 위의 경우에 태현이가 도착지까지 다다르기 위해서 총 6대의 버스를 타야 한다.
 태현이는 비행기를 타는데 돈을 거의 다 썼기 때문에 거쳐 가는 정류장의 개수를 최소한도로 줄여서
 태현이가 원더걸스가 묵고 있는 숙소까지 효율적으로 갈 수 있게 도와주자.

 

입력 형식                                     

 입력은 한줄로 이루어져 있고, 두 개의 숫자가 공백을 사이에 두고 입력된다.
 첫 번째 숫자는 태현이가 위치한 정류장의 번호고,
 두 번째 숫자는 태현이가 도착하고자 하는 정류장의 번호이다.
 두 숫자는 반드시 4자리의 0으로 시작 되지 않는 소수로 이루어져야 한다.

 

출력 형식                                     

태현이가 도착지 까지 가기위해 타게 되는 버스의 대수를 출력한다.

 

입력 예                                        

1033 8179

 

출력 예                                        

6

---

TravelWithPrimeNumber.h

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#include "../../Base.h"

using std::vector;
using std::queue;

class TravelWithPrimeNumber : public Base
{
private:
	struct Data
	{
	public:
		Data(int number, int count = 0) : number(number), count(count) {}

	public:
		int GetNumber() { return number; }
		int GetCount() { return count; }

	private:
		int number;
		int count;
	};

public:
	virtual void Code() override;

private:
	void FindPrimeNumbers();
	int GetCountToArrive();
	bool IsInRange(int number);
	bool IsPastNumber(int number);
	bool IsPrimeNumber(int number);

private:
	int a, b;
	vector<int> primeNumbers;
	vector<int> pastNumbers;
	queue<Data> q;
};

 

TravelWithPrimeNumber.cpp

void TravelWithPrimeNumber::Code()
{
	std::cin >> a >> b;

	FindPrimeNumbers();

	std::cout << GetCountToArrive();
}

/// <summary>
/// 아르스토테네스의 체로 4자리 소수를 찾는다.
/// </summary>
void TravelWithPrimeNumber::FindPrimeNumbers()
{
	bool numbers[10000];

	std::fill_n(numbers, 10000, true);

	// 0, 1은 제외해준다.
	numbers[0] = numbers[1] = false;

	for (int i = 2; i < 10000; i++)
	{
		if (numbers[i] == true)
		{
			primeNumbers.push_back(i);

			for (int j = i * 2; j < 10000; j += i)
			{
				numbers[j] = false;
			}
		}
	}
}

/// <summary>
/// 정류장을 이동하는 데 걸리는 최소 횟수를 찾아 반환한다.
/// </summary>
/// <returns>최소 이동 횟수</returns>
int TravelWithPrimeNumber::GetCountToArrive()
{
	q.push(Data(a));
	pastNumbers.push_back(a);

	int leastCount = 999'999'999;

	while (q.empty() == false)
	{
		Data curData = q.front();
		q.pop();

		int baseNumber = 0;
		int saveNumber = curData.GetNumber();
		for (int i = 1000; i > 0; i /= 10)
		{
			int restNumber = curData.GetNumber() % i;
			for (int j = 0; j < 10; j++)
			{
				int curNumber = baseNumber + i * j + restNumber;
				if (IsInRange(curNumber) == false)
				{
					continue;
				}

				if (IsPastNumber(curNumber))
				{
					continue;
				}

				if (IsPrimeNumber(curNumber) == false)
				{
					continue;
				}

				int curCount = curData.GetCount() + 1;
				if (leastCount < curCount)
				{
					continue;
				}

				if (curNumber == b)
				{
					leastCount = curCount;
					continue;
				}

				q.push(Data(curNumber, curCount));
				pastNumbers.push_back(curNumber);
			}

			int temp = i * (saveNumber / i);
			baseNumber += temp;
			saveNumber -= temp;
		}
	}

	return leastCount;
}

/// <summary>
/// 주어진 숫자가 4자리 숫자인지 검사한다.
/// </summary>
/// <param name="number">검사할 숫자</param>
/// <returns>조건 충족 여부</returns>
bool TravelWithPrimeNumber::IsInRange(int number)
{
	if (number < 1'000) return false;
	if (number > 9'999) return false;
	return true;
}

/// <summary>
/// 주어진 숫자가 소수인지 검사한다.
/// </summary>
/// <param name="number">검사할 숫자</param>
/// <returns>소수 여부</returns>
bool TravelWithPrimeNumber::IsPrimeNumber(int number)
{
	return std::find(primeNumbers.cbegin(), primeNumbers.cend(), number) != primeNumbers.cend();
}

/// <summary>
/// 주어진 숫자가 이전에 들어온 적 있는지 검사한다.
/// </summary>
/// <param name="number">검사할 숫자</param>
/// <returns>들어온 적 있는지 여부</returns>
bool TravelWithPrimeNumber::IsPastNumber(int number)
{
	return std::find(pastNumbers.cbegin(), pastNumbers.cend(), number) != pastNumbers.cend();
}

 

---

실행 결과 Success(100)

---

 

코드 해설

기본적으로 소수를 이용하는 문제이므로 이전에 사용했던 아리스토테네스의 체를 사용해 소수를 구해준다.

4 자릿수 소수를 구하면 되기 때문에 속도 저하는 생각하지 않아도 된다.

void TravelWithPrimeNumber::FindPrimeNumbers()
{
	bool numbers[10000];

	std::fill_n(numbers, 10000, true);

	// 0, 1은 제외해준다.
	numbers[0] = numbers[1] = false;

	for (int i = 2; i < 10000; i++)
	{
		if (numbers[i] == true)
		{
			primeNumbers.push_back(i);

			for (int j = i * 2; j < 10000; j += i)
			{
				numbers[j] = false;
			}
		}
	}
}

 

이후에는 BFS이므로 시작 위치로 주어진 숫자의 자릿수를 돌며 값을 바꿔서 소수인지 확인하는 과정을 거친다.

이 처리를 위해서 자리수를 분리해야 하므로 BaseNumber와 최초 값을 저장할 SaveNumber를 준비한다.

		int baseNumber = 0;
		int saveNumber = curData.GetNumber();

 

이후 첫 번째 자리수 부터 오른쪽으로 바꿔가며 값을 확인해 준다.

		for (int i = 1000; i > 0; i /= 10)
		{
			int restNumber = curData.GetNumber() % i;
			for (int j = 0; j < 10; j++)
			{
				int curNumber = baseNumber + i * j + restNumber;

 

해당 자리를 모두 확인했으면 기존 값을 baseNumber로 넣어서 최종적으로 한 자릿수만 바뀌도록 한다.

			int temp = i * (saveNumber / i);
			baseNumber += temp;
			saveNumber -= temp;

 

중복 체크는 모든 경로에 대해서 한 번에 처리하는데, BFS 특성상 기존에 확인했던 숫자가 다시 나온다면 그건 이미 이전에 더 효율적인 경로로 처리되었을 것이므로 새로 등장한 건 무시해야 하기 때문이다.

그렇지 않으면 중복 루트가 발생하기 때문에 굉장히 느려진다!

	pastNumbers.push_back(a);
    // ...
    				pastNumbers.push_back(curNumber);

 

이전 문제에서는 이 부분을 정확하게 파악하지 못해서 문제를 비판했는데, 내가 틀렸었다.

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제출처

Intermediate_Coder/그래프탐색-BFS/소수와 함께 하는 여행-JUNGOL