문제

문제 링크

해설

• 어려운 구현문제지만, 매초마다 해야 하는 일이 명확하게 적혀있기 때문에 주석을 활용해서 빠짐없이 코드로 구현합시다.
• 우선은 '벽'을 구현합니다. 주어지는 N보다 행과 열을 2칸씩 더 만든 뒤, for문 하나를 쓰면 쉽게 벽을 구현할 수 있습니다.
• 뱀은 가장 처음에 (1, 1)에서 움직이기 시작합니다.
• 방향은 →(0), ↓(1), ←(2), ↑(3)으로 표현하고, 다음 방향은 현재 방향에 +4를 더한 뒤 L은 1을 뺀 값에 4를 나눈 나머지, R은 1을 더한 값에 4를 나눈 나머지로 구할 수 있습니다.
• 한 번 움직일 때마다 머리와 꼬리 정보가 바뀌기 때문에, std::deque<>이 가장 사용하기 이상적인 자료구조입니다.
• 먼저 다음에 이동할 위치를 구한 뒤
  • 그곳이 벽인지 또는 자기 자신(뱀)인지 확인한 뒤
  • 꼬리를 먼저 옮기고,
  • 머리를 옮긴 뒤
  • 방향을 바꿔야 한다면 이제 옮깁니다. (주의하세요! 문제에 방향전환은 'X'초가 끝난 뒤에 이뤄진다고 나와있습니다! 미리 방향전환을 해버리면 안 됩니다!)

코드

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

constexpr int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
enum State {EMPTY, WALL, APPLE, SNAKE};

int N, K, L, curDir, board[102][102];
deque<pair<int, int>> snake;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N;
	for (int i = 0, j = N + 1; i <= j; ++i)	// 가장자리 벽 세우기
		board[0][i] = board[j][i] = board[i][0] = board[i][j] = State::WALL;
	
	cin >> K;
	for (int i = 0; i < K; ++i) {
		int y, x;
		cin >> y >> x;
		board[y][x] = State::APPLE;
	}
	snake.emplace_front(1, 1);
	board[1][1] = State::SNAKE;
	
	cin >> L;
	queue<pair<int, char>> cmds;
	for (int i = 0; i < L; ++i) {
		int t;
		char cmd;
		cin >> t >> cmd;
		cmds.emplace(t, cmd);
	}
	for (int time = 1, timeLimit = 10'000; time <= timeLimit; ++time) {
		// Calculate next head position.
		int cy = snake.front().first, cx = snake.front().second;
		int ny = cy + d[curDir][0], nx = cx + d[curDir][1];
		// Is the position wall or body of itself.
		if (board[ny][nx] == State::WALL || board[ny][nx] == State::SNAKE) {
			cout << time;		// Print answer
			break;
		}
        // Move tail to new position and remove tail 
		if (board[ny][nx] != State::APPLE) {
			board[snake.back().first][snake.back().second] = State::EMPTY;
			snake.pop_back();
		}
        // Move head to new position
		board[ny][nx] = State::SNAKE;
		snake.emplace_front(ny, nx);
        // Process command and change direction
		if (!cmds.empty() && time == cmds.front().first) {
			curDir = (cmds.front().second == 'L') ? ((curDir + 3) % 4) : ((curDir + 5) % 4);
			cmds.pop();
		}
	}
}

소스코드 링크

결과