[BOJ] 3190 : 뱀 (C++)

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

걸린 시간 : 56분

---

정말 그냥 구현 문제이다. 프로그램으로 상황을 잘 표현할 수 있다면 쉬운 문제이다.

나는 정말 사소한 부분에서 막혔다. 다음 부분이다.

if (find(apple.begin(), apple.end(), {ni, nj}))

apple이라는 벡터에서 {ni, nj} pair를 찾아 bool로 반환하는 algorithm 헤더의 함수이다.

하지만, pair는 기본 자료형이 아니므로 == operator가 정의되어 있지 않다. 즉, 애초에 같다는 것이 정의되어 있지 않아서 찾을 수가 없다는 것이다.

이를 위한 방법으로는 find_if 함수가 있다. 하지만, 어차피 find_if 함수가 시간복잡도가 낮은 것도 아니므로 코딩 테스트 목적으로는 find 함수를 직접 구현하는 것이 오히려 코드도 알아보기 쉽고 편할 것으로 생각됐다.

따라서 find 함수를 직접 구현했다.

정답코드

#include <bits/stdc++.h>
using namespace std;

int N, K, L, status = 0, sec = 0;
int di[4] = {0, 1, 0, -1};
int dj[4] = {1, 0, -1, 0};
vector<pair<int, int> > apple;
vector<pair<int, int> > snake;
queue<pair<int, char> > change;

bool find(pair<int, int> next) {
	for (int i = 0; i < apple.size(); i++) {
		pair<int, int> a = apple[i];
		if (next.first == a.first && next.second == a.second) {
			apple.erase(apple.begin() + i);
			return true;
		}
	}
	return false;
}

bool crushmyself(int ni, int nj) {
	for (auto s : snake) {
		if (ni == s.first && nj == s.second) {
			for (auto d : snake) {
			}
			return true;
		}
	}
	return false;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		apple.push_back({a-1, b-1});
	}
	cin >> L;
	for (int i = 0; i < L; i++) {
		int a;
		char b;
		cin >> a >> b;
		change.push({a, b});
	}
	snake.push_back({0, 0});
	while (true) {
		sec++;
		int ci = snake.back().first;
		int cj = snake.back().second;
		int ni = ci + di[status];
		int nj = cj + dj[status];
		if (ni < 0 || ni >= N || nj < 0 || nj >= N || crushmyself(ni, nj)) {
			cout << sec;
			return 0;
		}
		else if (find({ni, nj})) {
			snake.push_back({ni, nj});
		}
		else {
			snake.push_back({ni, nj});
			snake.erase(snake.begin());
		}
		
		if (change.front().first == sec) {
			if (change.front().second == 'L') {
				status--;
				if (status < 0) status += 4;
			}
			else if (change.front().second = 'D') {
				status++;
				if (status > 3) status -= 4;
			}
			change.pop();
		}
	}
	return 0;
}