[백준 BOJ][C++]14226번 이모티콘 풀이: BFS

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

14226번: 이모티콘

 

 

 이 문제는 BFS를 이용하여 해결할 수 있습니다. 

 

 queue에 푸시할 노드의 자료구조로써 구조체 node를 선언하였습니다. 

 

 w는 현재 화면의 이모티콘의 개수, c는 클립 보드의 이모티콘의 개수, depth는 현재 노드까지 걸린 시간(초)라고 할 수 있습니다. 

 

 visit[w][c] = 화면의 이모티콘의 개수가 w이고 클립 보드의 이모티콘의 개수가 c일 때의 방문 여부

 

 [풀이 과정]

1. 처음 시작 상태인 visit[1][0] = true로 방문 표시 후, w = 1, c = 0, depth = 0을 queue 에 푸시한다. 

2. queue에서 노드를 하나 pop하여 curr에 저장한다. 

3. 현재 노드에서 할 수 있는 연산(화면의 이모티콘을 클립보드에 복사, 클립보드의 이모티콘을 화면에 붙여넣기, 화면의 이모티콘 하나 삭제)에 대해 다음 w와 c가 0보다 크고 s보다 작거나 같고 아직 방문하지 않았다면 방문표시 후, queue에 푸시한다. 

4. 현재 노드의 w가 s와 같은 노드를 찾을 때까지 2~3과정을 반복한다. 

 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

#define MAX 1001

int s;
bool visit[MAX][MAX] = { false, };

typedef struct node {
	int w;
	int c;
	int depth;
};

int bfs() {
	queue<node> q;

	visit[1][0] = true;
	q.push({ 1, 0, 0 });

	while (!q.empty()) {
		node curr = q.front();
		q.pop();

		if (curr.w == s) {
			return curr.depth;
		}

		for (int i = 0; i < 3; i++) {
			int tc = curr.c;
			int tw = curr.w;

			if (i == 0) { //클립보드에 복사
				tc = curr.w;
			}
			else if (i == 1) { //화면에 붙여넣기
				tw = curr.w + curr.c;
			}
			else { //하나 삭제
				tw = curr.w - 1;
			}

			if (tc<=0 || tc>s || tw<0 || tw>s)
				continue;
			if (visit[tw][tc])
				continue;

			visit[tw][tc] = true;
			q.push({ tw, tc, curr.depth + 1 });
		}
	}
}

int main(void) {

	cin >> s;
	
	int ret = bfs();

	cout << ret;

	return 0;
}