백준 3190번(Gold 4)

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

이번 시간에는 시뮬레이션 문제인 백준 3190번을 풀어보겠습니다.

3190번: 뱀

 

#include <iostream>
#include <vector>

int direction_row[4] = { 0, 1, 0, -1 }; // 동 남 서 북
int direction_column[4] = { 1, 0, -1, 0 };
int play_game(std::vector<std::vector<int>>&, std::vector<std::pair<int, char>>&);

int main() {
	int size = 0; int apple_count = 0; int rotate_count = 0;
	std::cin >> size;
	std::vector<std::vector<int>> board(size + 2, std::vector<int>(size + 2, 0));
	for (int column = 0; column < size + 2; ++column) {
		int row = 0;
		while (row < size + 2) {
			if (column == 0 || column == size + 1) {
				board[row][column] = -1; // 벽을 -1로, 사과를 1로 뱀 몸을 2로 정의하기로 하였다.
			}
			else {
				board[row][column] = -1;
				row = size + 1;
				board[row][column] = -1;
			}
			row++;
		}
	}

	std::cin >> apple_count;
	for (int count = 0; count < apple_count; ++count) {
		int row; int column;
		std::cin >> row >> column;
		board[row][column] = 1;
	}

	std::cin >> rotate_count;
	std::vector<std::pair<int, char>> rotate;
	for (int count = 0; count < rotate_count; ++count) {
		int distance; char leftOrRight;
		std::cin >> distance >> leftOrRight;
		rotate.push_back(std::make_pair(distance, leftOrRight));
	}

	std::cout << play_game(board, rotate);
	return 0;
}
int play_game(std::vector<std::vector<int>>& board, std::vector<std::pair<int, char>>& rotate) {
	int count = 0; int row = 1; int column = 1;
	std::vector<std::pair<int, int>>route;
	route.push_back({ row, column });
	int direct = 0;
	board[row][column] = 2;

	int distance_current = 0;
	for (int i = 0; i < rotate.size(); ++i) {
		int distance = rotate[i].first - distance_current;
		distance_current = rotate[i].first;
		while (distance) {

			distance--;
			count++;
			if (board[row + direction_row[direct]][column + direction_column[direct]] == -1 || board[row + direction_row[direct]][column + direction_column[direct]] == 2) {
				return count;
			}

			else if (board[row + direction_row[direct]][column + direction_column[direct]] == 1) {
				board[row + direction_row[direct]][column + direction_column[direct]] = 2;
				route.insert(route.begin(), { row + direction_row[direct], column + direction_column[direct] });
			}
			else {
				for (int i = route.size() - 2; i >= 0; --i) {
					board[route[i + 1].first][route[i + 1].second] = 0;
					board[route[i].first][route[i].second] = 0;
					route[i + 1] = route[i];
				}
				board[route[0].first][route[0].second] = 0;
				route[0] = { row + direction_row[direct], column + direction_column[direct] };
				
				for (int i = 0; i < route.size(); ++i) {
					board[route[i].first][route[i].second] = 2;
				}
			}
			row += direction_row[direct];
			column += direction_column[direct];
		}
		char leftOrRight = rotate[i].second;
		if (leftOrRight == 'D') {
			direct++;
			if (direct > 3)
				direct = 0;
		}
		else if (leftOrRight == 'L') {
			direct--;
			if (direct < 0)
				direct = 3;
		}
	}

	while (true) {

		count++;
		if (board[row + direction_row[direct]][column + direction_column[direct]] == -1 || board[row + direction_row[direct]][column + direction_column[direct]] == 2) {
			return count;
		}

		else if (board[row + direction_row[direct]][column + direction_column[direct]] == 1) {
			board[row + direction_row[direct]][column + direction_column[direct]] = 2;
			route.insert(route.begin(), { row + direction_row[direct], column + direction_column[direct] });
		}
		else {
			for (int i = route.size() - 2; i >= 0; --i) {
				board[route[i + 1].first][route[i + 1].second] = 0;
				board[route[i].first][route[i].second] = 0;
				route[i + 1] = route[i];
			}
			board[route[0].first][route[0].second] = 0;
			route[0] = { row + direction_row[direct], column + direction_column[direct] };

			for (int i = 0; i < route.size(); ++i) {
				board[route[i].first][route[i].second] = 2;
			}
		}
		row += direction_row[direct];
		column += direction_column[direct];
	}

}

뱀 본체를 담는 부분을 deque등으로 구현 가능하겠지만, board에서 벽을 -1, 사과를 1, 뱀 본체를 2로 구현하고 표시하기 위해서는 queue나 stack으로는 제약이 있어서 vector로 구현하였다.

만약 list로 구현한다면, linked와 array사이에서는 뱀이 움직일 때 마다, 모든 요소를 수정해야하기 때문에, 값에 접근하기 편한 array로 짜는게 좋아보인다. linked는 값에 접근하기위해서 O(n)의 복잡도를 가지기 때문이다. 

 

유지보수 차원에서는 좋지 않은 코드로 추후에 수정이 필요하다.