[G4] 벡준 14226번 이모티콘 C++ 너비 우선 탐색, 우선순위 큐, 해시맵

리뷰

 

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

이중 해시맵을 사용하여 AC를 받은 문제

 

 

전역 변수

• s : 목표 이모티콘의 개수를 저장할 변수
• v : 방문 여부를 체크하기 위한 이중 해시맵, key는 둘다 정수이며 value는 bool타입으로 정의했다.
• Emo : 화면, 클립보드, 걸린 시간을 정의할 구조체, 걸린 시간을 기준으로 오름차순 정렬한다.

 

함수

1. bfs

int bfs()

 

이모티콘을 복사, 붙여넣기, 삭제를 진행하며 목표 개수까지의 최소 시간을 구하기 위한 함수

1. Emo타입의 우선순위 큐 pq를 초기화 한다.
2. 화면의 초기값 1, 클립보드의 초기값 0, 걸린 시간의 초기값 0을 push해준다.
3. 화면의 초기값 1, 클립보드의 초기값 0에 방문 표시를 해시맵 v에 진행해 준다.
4. pq가 빌 때 까지 while루프를 수행하며, 매 루프마다 요소를 한개씩 꺼내준다.
5. 정수형 변수 cw, cc, ct에 현재 화면의 이모티콘 개수, 클립보드의 이모티콘 개수, 걸린 시간을 파싱해 준다.
6. 기저 조건으로 cw가 s와 동일하다면 ct를 리턴해 준다.
7. 3가지 연산의 결과값이 아직 방문처리 되지 않았다면 연산의 결과값을 방문처리 후 pq에 push해준다.
8. 기저 조건에 도달할 때 까지 위 로직을 반복 수행해 준다.

 

문제풀이

1. s에 목표 이모티콘의 개수를 입력 받아준다.
2. bfs함수를 호출하고 리턴 값을 출력해 준다.

 

트러블 슈팅

1. 처음엔 1001 * 1001크기의 배열로 방문 처리를 진행했지만 일부 케이스에 문제가 있었다.
2. 따라서 이중 해시맵을 사용했더니 생각보다 시간과 공간 복잡도가 널널하게 AC를 받게 되었다.

 

참고 사항

• S개의 이모티콘을 만들지 못하는 경우는 없다.
• 시뮬레이션 시 1000보다 높은 값에서 값을 줄여나가는 경우도 있을 것 같다. (범위 조정을 잘해야 함)

 

정답 코드

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

int s;
unordered_map<int, unordered_map<int, bool>> v;
struct Emo {
	int w, c, t;
	bool operator<(const Emo& other) const {
		return t > other.t;
	}
};

int bfs() {
	priority_queue<Emo> pq;
	pq.push({ 1, 0, 0 });
	v[1][0] = 1;

	while (!pq.empty()) {
		Emo emo = pq.top(); pq.pop();
		int cw = emo.w, cc = emo.c, ct = emo.t;
		if (cw == s) return ct;

		if (!v[cw][cw]) {
			v[cw][cw] = 1;
			pq.push({ cw, cw, ct + 1 });
		}
		if (cc && abs(s - cw) > abs(cw + cc - s) && !v[cw + cc][cc]) {
			v[cw + cc][cc] = 1;
			pq.push({ cw + cc, cc, ct + 1 });
		}
		if (!v[cw - 1][cc]) {
			v[cw - 1][cc] = 1;
			pq.push({ cw - 1, cc, ct + 1 });
		}
	}
	return -1;
}

int main() {
	cin >> s;
	cout << bfs();
}