[G4] 백준 9019번 DSLR C++ BFS

리뷰

 

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

어디서 많이 풀어본 것 같은 문제, 처음엔 문자열로 접근했다가 보기 좋게 시간 초과를 받았다.

정수형으로 접근하니 AC를 받긴 했으나 가지치기가 더 필요해 보여 최적화는 아닌듯 하다.

 

 

전역 변수

• t : 테스트 케이스의 개수를 저장할 정수형 변수
• s, e : 각 테스트 케이스의 초기값과 목표값을 저장하기 위한 정수형 변수
• v : 방문 여부를 체크하기 위한 정수형 배열
• Cur : 현재 탐색 중인 숫자와 여태까지의 명령을 저장하기 위한 구조체

 

함수

1. bfs

string bfs()

 

너비 우선 탐색을 통해 목표 값을 찾고 사용한 명령어를 리턴하기 위한 힘수

1. Cur타입의 큐 q를 초기화 하고 초기값 s와 빈 문자열 ""를 넣어준다.
2. 초기값의 방문 처리를 체크해 준다.
3. 큐가 빌 때 까지 탐색을 시작하고, 매번 큐에서 요소를 하나씩 빼내어 준다.
4. 현재 값을 num, 여태까지의 명령어를 op로 초기화 해주고 num과 e가 같다면 op를 리턴해 준다.
5. 정수형 변수 D, S, L, R을 초기화 하고 해당 변수에 각 연산값을 저장해 준다.
6. D의 경우 num에 2배를 곱한 뒤 10000으로 나눈 값이다, 방문되어있지 않다면 큐에 추가한다.
7. S의 경우 num이 0이면 9999, 아니면 num - 1이다.
8. L의 경우 num을 1000으로 나눈 나머지에 10을 곱해주고, num을 1000으로 나눈 값을 더해준다.
9. R의 경우 num을 10으로 나눈 나머지에 1000을 곱해주고, num을 10으로 나눈 값을 더해준다.

 

문제풀이

1. t값을 입력 받고 t번의 반복문을 수행해 준다.
2. s, e값을 각각 입력 받고 이전 케이스에서 사용한 방문 배열을 memset메서드를 통해 초기화 해준다.
3. bfs함수를 호출하고 해당 함수의 리턴 값을 줄바꿈을 기준으로 출력해 준다.

 

참고 사항

S가 매번 큐에 삽입되는 것과 모듈러 연산이 잦은 것이 성능에 크게 영향을 미칠 것 같다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

int t, s, e, v[10000];
struct Cur {
	int num;
	string op;
};

string bfs() {
	queue<Cur> q;
	q.push({ s, "" });
	v[s] = 1;

	while (!q.empty()) {
		Cur cur = q.front(); q.pop();
		int num = cur.num;
		string op = cur.op;
		if (num == e) return op;

		int D, S, L, R;
		D = num * 2 % 10000;
		if (!v[D]) {
			v[D] = 1;
			q.push({ D, op + 'D' });
		}

		S = num > 0 ? num - 1 : 9999;
		if (!v[S]) {
			v[S] = 1;
			q.push({ S, op + 'S' });
		}

		L = num % 1000 * 10 + num / 1000;
		if (!v[L]) {
			v[L] = 1;
			q.push({ L, op + 'L' });
		}

		R = num % 10 * 1000 + num / 10;
		if (!v[R]) {
			v[R] = 1;
			q.push({ R, op + 'R' });
		}
	}
	return "CANT";
}

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

	cin >> t;
	while (t--) {
		cin >> s >> e;
		memset(v, 0, sizeof(v));
		cout << bfs() << "\n";
	}
}