백준 14226 - 이모티콘(C++)

문제 링크입니다 https://www.acmicpc.net/problem/14226

14226번: 이모티콘

문제 조건

출력 예시

방문한 위치를 1차원 배열이 아닌 2차원 배열을 이용해서 확인해야되는 문제였습니다

 

문제 접근 방법

1. 현재 가지고 있는 스티커의 갯수를 통해서 3가지의 방법을 확인한다.

2. S개의 이모티콘이 만들어졌을 경우, 시간을 return 한다.

 

문제 접근 방법 - 1번(BFS() 함수를 참고해주세요)

현재 N개의 이모티콘에서 갈 수 있는 방법은 3가지 입니다.

1. check[N][N]이 0일 경우, N개일때 copy된 이모티콘이 N개 인적이 없다는 의미임으로 해당 결과를 queue에 넣는다.

2. check[N-1][copy]가 0일 경우, 1칸 없애도 됨으로 queue에 넣는다

3. check[N+copy][copy]가 0일 경우, 해당 과정을 queue에 넣어준다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int S;
int check[2001][1001];
typedef struct qu {
	int x; // 현재 이모티콘의 갯수
	int t; // 걸린 시간
	int copy; // 복사된 이모티콘이 갯수
};

int bfs() {
	check[1][0] = 1;
	queue<qu> q;
	q.push({ 1,0,0 });
	while (!q.empty()) {
		int x = q.front().x;
		int t = q.front().t;
		int copy = q.front().copy;
		q.pop();
		if (x == S) return t;
		if (x > 0 && x < 2001) {
			if (check[x][x] == 0) {
				check[x][x] = 1;
				q.push({ x,t + 1,x });
			}
			if (check[x - 1][copy] == 0) {
				check[x - 1][copy] = 1;
				q.push({ x - 1, t + 1, copy });
			}
		}
		if (x + copy < 2001 && x > 0) {
			if (check[x + copy][copy] == 0) {
				check[x + copy][copy] = 1;
				q.push({ x + copy, t + 1,copy });
			}
		}
	}
}

void solve() {
	int ans = bfs();
	cout << ans;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> S;
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요!