[G4] 백준 1963번 소수 경로 C++ 너비 우선 탐색, 에라토스테네스의 체

리뷰

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

에라토스테네스의 체... 오랜만에 접했더니 소수 판정에서의 엣지 케이스를 제대로 잡지 못했었다.

그 외에는 소수를 문자열로 변환시켜 해시맵의 key로 활용하면 금방 풀 수 있는 문제

 

 

전역 변수

• t : 주어지는 테스트 케이스의 개수를 저장할 정수형 변수
• sosu : 초기 소수 정보를 저장하기 위한 정수형 배열
• s : 각 테스트 케이스 마다 주어지는 시작 소수를 저장할 문자열 변수
• e : 각 테스트 케이스 마다 주어지는 목표 소수를 저장할 문자열 변수
• Cur : 시뮬레이션 시 사용할 현재 문자열과 시간을 정의하기 위한 구조체
• dic : 소수 정보를 문자열로 파싱하여 저장하기 위한 해시맵

 

함수

1. bfs

int bfs()

 

시작 소수로부터 도착 소수로 까지의 걸리는 시간을 구하는 함수

1. Cur타입의 큐 q를 초기화 하고, 초기 문자열 s와 초기 시작 0을 인자로 push한다.
2. 방문 처리를 위한 string, bool타입의 해시맵 v를 초기화 해주고, 시작 소수에 방문 처리를 해준다.
3. q가 빌 때 까지 루프를 돌며 각 루프마다 요소를 한개씩 꺼내어 준다.
4. 기저조건으로 만약 현재 문자열이 목표 문자열에 도달했을 경우 걸린 시간을 리턴해 준다.
5. 1000 ~ 9999의 수이므로 각 인덱스를 바꿔주어야 하니 4번의 for문을 수행해 준다.
6. 이후 0 ~ 9까지의 문자를 순회하며 현재 문자열을 새로운 문자열 변수 nstr에 저장해 준다.
7. nstr의 현재 인덱스를 새로운 문자로 교체해 준다.
8. 만약 nstr이 dic에 존재하지 않거나 방문처리가 되어 있다면 continue처리해 준다.
9. 위 조건에 만족하지 않는다면 nstr을 방문처리 해 주고, nstr과 증가된 시간을 큐에 추가해 준다.
10. 만약 while루프가 종료될 때까지 기저조건에 도달하지 못했다면 -1을 리턴해 준다.

 

문제풀이

1. sosu배열에 에라토스테네스의체를 통해 소수가 아닌 값들은 모두 1로 변경해 준다.
2. 소수인 값들은 해당 값을 to_string메서드를 통해 문자열로 변환 후 dic의 key로, value는 true로 저장한다.
3. t를 입력 받고 t번 루프를 돌며 시작 소수 s와 도착 소수 e를 입력 받아준다.
4. bfs를 호출하고 시작 소수로 부터 도착 소수까지 변환 시간의 최소값을 정수형 변수 result에 받아준다.
5. 만약 result가 -1이라면 Impossible를, 아니라면 result를 출력해 준다.
6. 3 ~ 5번 로직을 테스트케이스가 종료될 때 까지 반복해 준다.

 

트러블 슈팅

첫 시도 시 예제는 모두 맞았으나 에라토스테네스의 체를 구현할 때 두번째 for문의 범위가 잘못되어 제대로 된 소수를 구하지 못했다.

1만 까지의 소수를 구하는 식은 다음과 같다.

for (int i = 2; i * i < 10000; ++i) {
    if (!sosu[i]) {
        for (int j = i * i; j < 10000; j += i) sosu[j] = 1;
    }
}

 

 

참고 사항

문자열의 길이가 짧은 편이라 현재 소수의 값을 문자열로 파싱하여도 시간 및 공간 복잡도에 큰 영향은 주지 않았다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<string>
#include<unordered_map>
#include<vector>
using namespace std;

int t;
int sosu[10000];
string s, e;
struct Cur {
	string str;
	int c;
};
unordered_map<string, bool> dic;

int bfs() {
	queue<Cur> q;
	q.push({ s, 0 });
	unordered_map<string, bool> v;
	v[s] = true;

	while (!q.empty()) {
		Cur cur = q.front(); q.pop();
		string str = cur.str;
		int cc = cur.c;
		if (str == e) return cc;

		for (int i = 0; i < 4; ++i) {
			for (char j = '0'; j <= '9'; ++j) {
				string nstr = str;
				nstr[i] = j;
				if (!dic[nstr] || v[nstr]) continue;
				v[nstr] = true;
				q.push({ nstr, cc + 1 });
			}
		}
	}
	return -1;
}

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

	for (int i = 2; i * i < 10000; ++i) {
		if (!sosu[i]) {
			for (int j = i * i; j < 10000; j += i) sosu[j] = 1;
		}
	}

	for (int i = 1000; i < 10000; ++i) {
		if (!sosu[i]) dic[to_string(i)] = true;
	}

	cin >> t;
	while (t--) {
		cin >> s >> e;
		int result = bfs();
		if (result == -1) cout << "Impossible\n";
		else cout << result << "\n";
	}
}