[G4] 백준 24955번 숫자 이어 붙이기 C++ 너비 우선 탐색

리뷰

 

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

문자열을 통해 숫자를 이어 붙이기를 구현했다.

 

 

전역 변수

• MOD : 모듈러 연산을 위한 상수 변수
• N : 배열의 최대 크기를 정의할 상수 변수
• n : 집의 개수를 저장할 변수
• q : 쿼리의 개수를 저장할 변수
• nodes : 대문에 쓰여있는 수를 저장할 배열
• v : 방문 여부를 체크하기 위한 배열
• edges : 인접 리스트를 저장하기 위한 벡터 배열
• P : 현재 노드 node와 이어 붙인 수 cv를 정의할 구조체

 

함수

1. bfs

string bfs(int sn, int en)

 

너비 우선 탐색을 통해 시작 지점부터 목표 지점까지 방문하며 이어 붙인 수를 구하기 위한 함수

1. 매개 변수로 시작 지점의 번호 sn, 도착 지점의 번호 en을 전달 받는다.
2. P타입의 큐 q를 초기화 하고, 시작 지점의 번호 sn, 해당 지점의 대문에 쓰여있는 수 nodes[sn]을 push한다.
3. 시작 노드에 방문처리 후 q가 빌 때 까지 while 루프를 순회한다.
4. 매 루프마다 요소를 꺼내주고, 만약 현재 노드 cn이 en에 도달했다면 현재 이어 붙인 수 cv를 리턴한다.
5. 기저 조건에 해당하지 않는다면 인접 리스트를 순회하며 방문하지 않은 노드로의 이동을 진행한다.
6. 이동 진행 후엔 cv에 해당 노드의 대문에 쓰여있는 수를 더해 변수 nv에 저장해 준다.
7. nv를 정수형으로 변경한 값이 MOD보다 크다면 MOD로 나눈 나머지를 nv에 저장해 준다.
8. q에 다음 노드 nn과 새로운 이어 붙인 수 nv를 push해준다.

 

문제풀이

1. n, q에 값을 입력 받고, n개의 노드를 순회하며 nodes배열에 대문 앞에 쓰인 수를 저장ㅈ해 준다.
2. n - 1개의 간선을 입력 받고, 양방향 간선으로 인접 리스트를 초기화 해준다.
3. q개의 쿼리를 받아 변수 a, b에 노드 번호를 입력 받고, memset 메서드를 통해 v배열을 초기화 해준다.
4. bfs함수에 a, b를 매개 변수로 전달하여 a에서 b로 가면서 이어 붙인 수를 리턴하고 해당 값을 출력해 준다.

 

트러블 슈팅

1. long long타입으로는 최악의 케이스 10000000001000000000을 정수형으로 변환할 수 없었다.
2. unsigned long long타입을 사용해 주면 위 최악의 케이스를 정수형으로 변환할 수 있었다.
3. 따라서 long long타입을 unsigned long long으로, 정수 파싱을 stoull 메서드를 통해 진행해 AC를 받았다.

 

참고 사항

• long long은 약 9 * 1e18, unsigned long long은 약 18 * 1e18범위의 정수를 담을 수 있다.

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<cstring>
#define ull unsigned long long
using namespace std;

const ull MOD = 1000000007;
const int N = 1001;
int n, q;
string nodes[N];
bool v[N];
vector<int> edges[N];
struct P {
	int cn;
	string cv;
};

string bfs(int sn, int en) {
	queue<P> q;
	q.push({ sn, nodes[sn] });
	v[sn] = true;

	while (!q.empty()) {
		P p = q.front(); q.pop();
		int cn = p.cn;
		string cv = p.cv;
		if (cn == en) return cv;

		for (int nn : edges[cn]) {
			if (v[nn]) continue;
			v[nn] = true;
			string nv = cv + nodes[nn];
			ull nvi = stoull(nv);
			if (nvi > MOD) nv = to_string(nvi % MOD);
			//cout << nv << "\n";
			q.push({ nn, nv });
		}
	}
	return "-1";
}

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

	cin >> n >> q;
	for (int i = 1; i <= n; ++i) cin >> nodes[i];
	for (int i = 1; i <= n - 1; ++i) {
		int a, b; cin >> a >> b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	while (q--) {
		int a, b; cin >> a >> b;
		memset(v, 0, sizeof(v));
		cout << bfs(a, b) << "\n";
	}
}