[2차원 bfs] 14226 이모티콘

이모티콘 (14226)

 

풀이코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
// 14226 이모티콘
const int MAX = 2500;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 

	int n;
	
	queue<pair<int, int>> q;
	int dist[MAX + 1][MAX + 1];
	fill_n(&dist[0][0], (MAX + 1) * (MAX + 1), -1);
	cin >> n;
	
	// (s, c) : (화면엔 s 개, 클립보드엔 c 개) 이모티콘 -> 2차원 정점
	q.push(make_pair(1, 0));
	dist[1][0] = 0;
	while(true){
		pair<int, int> currentNode = q.front();
		q.pop();
		
		int s = currentNode.first;
		int c = currentNode.second;
	
		pair<int, int> nextPairs[3] = {
			make_pair(s, s),
			make_pair(s + c, c),
			make_pair(s - 1, c)
		};
		
		for(pair<int, int> nextNode : nextPairs){
			int ns = nextNode.first;
			int nc = nextNode.second;
			// 범위 벗어나는지 체크
			if(ns > 0 && ns < MAX && nc < MAX){
				if(dist[ns][nc] == -1){
					q.push(nextNode);			
					dist[ns][nc] = dist[s][c] + 1;				
				}
			}
			// 기저 사례 : 화면의 이모티콘이 input 과 같아지면 출력
			if(ns == n){
				cout << dist[ns][nc] << '\n';
				return 0;
			}
		}

	}
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. 화면에 있는 이모티콘 s 개 / 클립보드에 있는 이모티콘 c 개

- 정점의 정의는 (s,c) 2차원이라고 볼 수 있다.

(BFS 에서 하나의 정점이 서로 다른 두 개의 정보를 저장하고 있으면 안되므로, 1차원으로는 2개의 정보를 저장할 수 없다. 그러므로, 2차원으로 늘려 독립적인 정보를 저장케 한 것이다.)

2. s 의 최대가 1000 c 도 1000 이므로 최대 1,000,000 이다. BFS 로 충분히 가능.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. OutOfBound 오류가 발생했었다. s, c 모두 1000 이하 이지만, s + c 연산이 있으므로 최대 2000 이 나올 수 있다는 점을 고려했어야 했다.