백준 3190 - 뱀

문제링크

• 백준 3190

문제설명

• NxN 정사각 보드 위에 사과가 놓여있고, 뱀은 맨위 맨좌측에 길이가 1인 상태로 위치하고 있다.
• 뱀은 처음에는 오른쪽을 향한다.
• 뱀 이동 규칙
  • 몸길이를 1 늘려서 머리를 다음 칸에 위치시킨다.
  • 벽이나 자기 자신의 몸과 부딪히면 게임 끝
  • 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
  • 이동한 칸에 사과가 없다면, 꼬리가 위치한 칸을 비워준다. (몸 길이는 변하지 않는다.)
• 사과의 위치와 뱀의 이동 경로가 주어질 때 게임이 몇 초에 끝나는지 계산

입력

• 보드의 크기 N (2~100)
• 사과의 개수 K
• K개의 줄에 사과의 위치 (맨위 맨좌측은 1행 1열)
• 다음 줄에는 뱀의 방향 변환 횟수 L (1~100)
• L개의 줄에 정수 X, 문자 C가 주어지는데, X초(1~10,000)가 지난 후 왼쪽(C가 ‘L’), 오른쪽(C가 ‘D’)

문제접근방향

• board[N+1][N+1]을 만들어서 1행1열 ~ N행N열을 나타낼 수 있도록 한다.
  • 빈칸은 0, 뱀이 존재하는 칸은 1, 사과는 2로 설정한다.
• 뱀이 존재하는 칸의 정보를 담는 구조체를 만든다.
  • int x, int y, int head
  • head(0): 오른쪽, head(1): 왼쪽, head(2): 아래쪽, head(3): 위쪽
• 위 구조체를 변수로 담는 큐(queue)를 선언한다.
  • 큐의 첫번째 원소는 항상 tail 이다.
  • 큐의 마지막 원소는 머리의 위치와 방향 정보를 담는다.
• direction[L+1] 을 선언해서 direction[1]은 1초일 때 방향 전환을 나타내도록 한다.
  • direction[x]==0: 방향 전환 x, direction[x]==L: 왼쪽 방향 전환, direction[x]==D: 오른쪽 방향 전환

---

1. 현재 head 방향을 확인힌다.
2. 뱀의 다음 좌표를 계산한다.
3. board[next_x][next_y] 에 위치한 정보를 확인한다.
   • 빈칸(0): 해당 좌표를 큐에 담고, q[0]은 pop하고 빈칸(0)으로 만든다.
   • 자기자신(1) or 범위를 벗어난다: 탐색을 종료하고 경과한 시간을 출력한다.
   • 사과(2): 해당 좌표를 큐에 담는다.
4. 벰의 다음 head 방향을 결정한다.
5. 1~4 과정을 탐색종료가 될때까지 반복하며, 반복문 한번 당 time을 1씩 증가시킨다.

구현

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

typedef struct _node {
	int x;
	int y;
	int head; // head(0): 오른쪽, head(1): 왼쪽, head(2): 아래쪽, head(3): 위쪽
} Node;

// 방향에 따른 dx, dy
int movement[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

int change_direction(int head, char c) {

	switch (head) {
	case 0:
		if (c == 'D') return 2;
		else if (c == 'L') return 3;
		else return head;
		break;
	case 1:
		if (c == 'D') return 3;
		else if (c == 'L') return 2;
		else return head;
		break;
	case 2:
		if (c == 'D') return 1;
		else if (c == 'L') return 0;
		else return head;
		break;
	case 3:
		if (c == 'D') return 0;
		else if (c == 'L') return 1;
		else return head;
		break;
	}
}

// 빈칸(0)이면 해당 좌표를 큐에 담고, q[0]을 pop하여 tail을 바꿔준다.
// 자기자신(1)이면 탐색을 종료한다.
// 사과(2)이면 해당 좌표를 큐에 담는다.
bool update_board(vector<vector<int>>& board, queue<Node>& q, int head, int x, int y) {
	int N = board[0].size() - 1;
	if (x >= 1 && x <= N && y >= 1 && y <= N) {
		if (board[x][y] == 0) {
			board[x][y] = 1;
			board[q.front().x][q.front().y] = 0;

			Node nnode = { x, y, head };
			q.push(nnode);
			q.pop();
			return true;
		}
		else if (board[x][y] == 1) {
			return false;
		}
		else if (board[x][y] == 2) {
			board[x][y] = 1;
			Node nnode = { x, y, head };
			q.push(nnode);
			return true;
		}
	}
	else return false;
}

int move_snake(vector<vector<int>>& board, vector<char>& direction, queue<Node>& q) {
	int time = 0;

	int cur_head = q.back().head;
	int next_head = cur_head;
	while (true) {
		time += 1;
		cur_head = next_head;
		int next_x = q.back().x + movement[cur_head][0];
		int next_y = q.back().y + movement[cur_head][1];
		if (update_board(board, q, cur_head, next_x, next_y) == false) break;
		next_head = change_direction(cur_head, direction[time]);
	}

	return time;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int N;
	cin >> N;
	// 빈칸(0), 뱀(1), 사과(2)
	vector<vector<int>> board(N+1, vector<int>(N+1, 0));

	int K;
	cin >> K;
	for (int line = 0; line < K; line++) {
		int x, y;
		cin >> x >> y;
		board[x][y] = 2;
	}

	int L;
	cin >> L;
	vector<char> direction(10001);
	
	for (int line = 0; line < L; line++) {
		int x; char c;
		cin >> x >> c;
		direction[x] = c;
	}

	queue<Node> q;
	Node first = { 1, 1, 0 }; // 초기 상태(x=1, y=1, head=0)
	q.push(first);

	int ans = move_snake(board, direction, q);
	cout << ans << endl;
	return 0;
}

구현2 (2024.03.20 updated)

#include <iostream>
#include <queue>
#include <vector>
#include <memory.h>

#define MAX_N 101
#define MAX_TIME 10001

#define EMPTY 0
#define APPLE 1
#define SNAKE 2

#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
using namespace std;

int N, K;
int board[MAX_N][MAX_N];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
char timeTable[MAX_TIME];

int getNextDirection(int chead, char rotate)
{
	if (rotate == 'L') {
		if (chead == UP) return LEFT;
		if (chead == RIGHT) return UP;
		if (chead == DOWN) return RIGHT;
		if (chead == LEFT) return DOWN;
	}
	else if (rotate == 'D') {
		if (chead == UP) return RIGHT;
		if (chead == RIGHT) return DOWN;
		if (chead == DOWN) return LEFT;
		if (chead == LEFT) return UP;
	}
	else return chead;
}

int solution()
{
	queue<pair<int, int>> q;
	board[1][1] = SNAKE;
	int head = RIGHT;
	q.push(make_pair(1, 1));

	int ctime = 0;
	int nx = 1, ny = 1;
	while (true) {
		ctime++;
		nx += dx[head];
		ny += dy[head];
		if (nx <= 0 || nx > N || ny <= 0 || ny > N) break;
		if (board[nx][ny] == SNAKE) break;
		q.push(make_pair(nx, ny));
		if (board[nx][ny] == EMPTY) {
			board[q.front().first][q.front().second] = EMPTY;
			q.pop();
		}
		board[nx][ny] = SNAKE;
		head = getNextDirection(head, timeTable[ctime]);
	}
	return ctime;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> N >> K;

	memset(board, EMPTY, sizeof(board));
	for (int i = 0; i < K; i++) {
		int row, col;
		cin >> row >> col;
		board[row][col] = APPLE;
	}

	int L;
	int X;
	char C;
	cin >> L;
	for (int i = 0; i < L; i++) {
		cin >> X >> C;
		timeTable[X] = C;
	}
	int ans = solution();
	cout << ans << endl;
}