[C++] 백준 14226 : 이모티콘

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

14226번: 이모티콘

 

 

bfs visit을 체크할 때는 현재상태가 고려되어야 하는 것이므로

현재상태를 나타내는 num(스크린의 이모티콘 개수)와 clip(클립보드의 이모티콘 개수) 가 모두 고려되어야 함

-> visit을 2차원 배열로 둠

 

애초에 이 문제를 bfs로 풀어도 되는 이유가 왔던 상태 라면 굳이 또 안와도 되는(visit을 체크해 주는)게 의미가 있기 때문이다

 

 

https://www.acmicpc.net/board/view/30100

글 읽기 - 틀렸습니다. 라고 나오는데 어느 부분이 문제인지 모르겠습니다.

 

 

 

(cur / cur) visit 체크 안해준 이유는 cur가 이미 in bound이기 때문에 어차피 true라서 안해줌

 

범위에 관해서는.. 굳이 2천까지 잡을 필요 없지만 2천으로 하면 넉넉하겠다 싶어서 2천으로 잡음..

 

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

int S;
//num, clipboard
bool visit[2000][2000];
struct info {
	int num, clip, cnt;
};

bool in_bound(int x, int y) {
	if (x < 0 || x >= 2000 || y < 0 || y >= 2000) return false;
	return true;
}

int bfs() {
	queue<info> q;
	q.push({1, 0, 0});
	visit[1][0] = true;

	while (!q.empty()) {
		int cur = q.front().num;
		int clip = q.front().clip;
		int cnt = q.front().cnt;
		q.pop();

		if (cur == S) return cnt;
		
		if (!visit[cur][cur]) {
			visit[cur][cur] = true;
			q.push({ cur, cur, cnt + 1 });
		}
		if (in_bound(cur + clip, clip) && !visit[cur + clip][clip]) {
			visit[cur + clip][clip] = true;
			q.push({ cur + clip, clip, cnt + 1 });
		}
		if (in_bound(cur - 1, clip) && !visit[cur - 1][clip]) {
			visit[cur - 1][clip] = true;
			q.push({ cur - 1, clip, cnt + 1 });
		}
	}
	return -1;
}

int main() {
	scanf("%d", &S);
	printf("%d", bfs());
}

 

 

 

이 문제가 https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

랑 비슷하지만 다른 점은 이모티콘 문제는 상태를 나타내는 변수가 두개이고 숨바꼭질은 하나라는 거다

 

숨바꼭질2에서도 - 로 움직이는 연산이 있기 때문에

max인 100,000 이상으로 잡아줘야 할 거 같지만

어차피 그 초과인 값으로는 아예 접근조차 못하는거기 때문에

안그래도 줘도 된다..