[BOJ/C++] 3190번 - 뱀

1. 문제 링크

BOJ 3190번 - 뱀

2. 걸린 시간

50분

3. 문제

4. 문제 풀이

• 먼저 뱀의 몸길이를 늘려 머리를 다음 칸에 위치함
• 벽이나 뱀의 몸에 부딪히면, 게임 끝
• 사과가 있다면, 뱀의 몸 길이를 늘림
• 사과가 없다면, 뱀의 몸 길이는 늘리지 않고 꼬리를 한 칸 앞으로 당김
• 특정한 시간(초)에 도달하면, 방향을 왼쪽(L) 혹은 오른쪽(D)으로 꺾어야 함

이 문제는 고려해야 할 요소가 많다.

1. 뱀이 칸을 벗어나는지
2. 뱀의 몸에 부딪히는지
3. 뱀이 사과를 만나는지
4. 뱀의 방향을 전환해야 하는지

왼쪽 그림은 테스트케이스 1번을 나타낸 것이다.

• 3초일 때, 오른쪽(D)로 한 번 꺾음
• 5초일 때, 사과를 만나서 몸길이가 2가 됨
• 9초일 때, 벽에 부딪혀서 게임 끝

방향을 구현하기 위해서 동(0), 남(1), 서(2), 북(3)으로 나타내었고, 각각의 방향에서 왼쪽(L)과 오른쪽(D)으로 꺾는 것을 구현하기 위해 계산식을 썼다.

vector<pair<int, int>> dir = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

// ...

// 여기서 d는 현재의 뱀의 방향이고
// it는 {회전시간, 방향}을 가리키는 iterator
if (it->second == 'L')  // 왼쪽으로 회전해야 한다면 
    d = (d + 3) % 4;
else  // 오른쪽으로 회전해야 한다면 
    d = (d + 1) % 4;

이정도만 정하고 구현 들어가도 충분하다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, K, L, sec = 0;
vector<pair<int, int>> dir = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
vector<pair<int, int>> apple;
vector<pair<int, char>> trans;
vector<pair<int, int>> snake = {make_pair(0, 0)};

int shift(int x, int y, int d) {
   // 방향 전환해야 하는지 확인
   auto it = find_if(trans.begin(), trans.end(), [](const pair<int, char>& t) {
       return t.first == sec;  // 현재의 시간과 일치하는지 확인 
       });
   
   if (it != trans.end()) {  // 방향 전환 해야한다면 
       if (it->second == 'L')  // 왼쪽으로 회전해야 한다면 
           d = (d + 3) % 4;
       else
           d = (d + 1) % 4;
   }

   int nx = x + dir[d].first, ny = y + dir[d].second;

   if (nx < 0 || nx >= N || ny < 0 || ny >= N) return ++sec;
   if (find(snake.begin(), snake.end(), make_pair(nx, ny)) != snake.end()) return ++sec;

   sec++;
   snake.push_back(make_pair(nx, ny)); // 뱀의 위치 추가 
    
   auto iter = find(apple.begin(), apple.end(), make_pair(nx, ny));

   // 이동할 위치에 사과가 없다면 길이 유지
   if (iter == apple.end())
       snake.erase(snake.begin());  // 뱀의 꼬리 제거
   else
       apple.erase(iter);

   return shift(nx, ny, d);
}

int main() {
   cin >> N >> K;

   int a, b;
   for (int i = 0; i < K; i++) {
       cin >> a >> b;
       apple.push_back(make_pair(a-1, b-1));
   }

   cin >> L;

   int x;
   char c;
   for (int i = 0; i < L; i++) { 
       cin >> x >> c;
       trans.push_back(make_pair(x, c));
   }

   cout << shift(0, 0, 0) << '\n'; 
}

5. 배운 점

람다식

{시간, 회전방향} 형식을 저장하는 벡터인 trans에서 현재 시간 sec과 같은 경우의 '회전방향'을 찾고 싶었다.

그래서 처음에는 다음과 같이 작성했었다.

auto it = find(trans.begin(), trans.end(), sec);

그랬더니 pair<int, char>과 int형은 비교할 수가 없으므로 에러가 발생했다.

auto it = find_if(trans.begin(), trans.end(), [](const pair<int, char>& t) {
	return t.first == sec;
    });

• trans.begin()부터 trans.end()까지 순회하면서
• 각각의 요소 t에 대해 t.first == sec인지를 확인
• 조건을 만족하는 첫 번째 요소의 iterator을 반환

동작 구조

1. trans.begin()부터 trans.end()까지 순회
2. 각 원소를 람다 함수에 전달
   [](const pair<int, char>& t) { return t.first == sec; }
3. 해당 람다가 true를 반환하면, 그 시점의 iterator를 find_if()가 반환
4. 끝까지 true가 나오지 않으면, trans.end()를 반환 (= 못 찾음)

Q. [](const pair<int, char>& t)에서 &를 쓰는 이유는?
A. 이렇게 하면 t는 pair<int, char> 객체를 복사하지 않고 참조만 한다. 즉, 성능의 최적화를 위함이다.

Q. 그러면 const는 왜 붙이는거냐?
A. const는 해당 객체를 수정하지 않겠다는 선언인데, 코드 안정성과 호환성을 위해 붙인다. std::find_if() 같은 STL 함수는 종종 내부에서 const 객체를 넘기기 때문에 람다 파라미터도 const&를 받아야 타입이 맞다.

🔗 람다 함수란?