백준 No.3190 [뱀]

BOJ No.3190 [뱀]

---

  문제 

3190번: 뱀 (acmicpc.net)

3190번: 뱀

---

  설명 

 <알고리즘 분류> 
 * 구현

    우선순위 큐 와   셋 을 사용하여 구현을 해서 풀었다.

 

  게임이 끝나는 조건은 두 가지 조건이 있다.

   1. 벽과 만나는 경우 -> 현재 위치가 맵을 벗어났을 때 현재 시간을 return 하였다.

   2. 몸과 부딪히는 경우 -> 현재 몸이 있는 좌표들을 set<pair<int, int>> 에 추가하여 몸과 부딪히는 여부를 파악하였다.

      2-1) 현재 좌표에 해당하는 set 이 이미 있다면, 몸과 부딛힌 경우이므로 현재 시간을 return 하였다.

      2-2) 현재 좌표에 해당하는 set 이 없다면 몸과 부딛히지 않은 경우이므로 현재 좌표에 대한 set 을 추가함으로써 뱀 머리를 두었다.

 

   방향 변환에 대한 정보는 계속해서 현재 있는 방향변환정보들 중 가장 빠른 시간에 일어나는 정보만 알면 되므로 우선순위큐(내림차순)를 통해 방향변환정보를 저장해두고, 매 시간마다 현재 시간에 대한 방향전환정보가 있는지 파악을 하였다.

 

  뱀의 길이가 늘어나고 안 늘어나고 또한 우선순위큐를 이용해 관리를 하였다. 현재 위치에 사과가 있다면 뱀의 꼬리는 자르지 않고 그냥 계속 진행하면 된다. 하지만 현재 위치에 사과가 없다면 가장 꼬리를 제거해야 한다. 가장 꼬리에 대한 좌표는 현재 몸통에 해당되는 좌표들 중 가장 이른 시간에 방문하게 된 좌표이다. 그래서 꼬리에 대한 좌표를 파악하기 위해 이 경우에도 우선순위큐(내림차순)을 사용하였다.  따라서, 뱀의 몸에 대해서는 위에서 설명된 set 과 현재 설명하는 우선순위큐(내림차순)을 사용하였다.

 

 <정리> 

1. 게임이 끝나는 조건
   1-1) 벽과 만나는 경우 : 현재 위치가 맵을 벗어난 경우
   1-2) 몸과 부딪히는 경우 : 현재 위치에 대한 set 이 이미 존재하는 경우

2. 방향 변환에 대한 정보 : 정보의 시간에 대해 내림차순 우선순위큐를 이용하여 파악

3. 뱀의 길이에 대한 작업 : 현재 뱀에 해당하는 좌표들을 각 좌표들에 방문된 시간에 대한 내림차순 우선순위큐에 추가한다. 그렇게 하면 우선순위큐의 top 에는 뱀의 몸에서 가장 이르게 방문된 몸(즉, 가장 꼬리)이 된다.
     현재 위치에 사과가 없다면 이 꼬리를 제거하면 된다.

---

  Code 

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#define ground -1
#define row first
#define col second

using namespace std;
typedef pair<int, int> pii;
typedef pair<int, char> pic;

enum {
	Right = 0, Down, Left, Up
};

struct SNAKE {
	int r, c;
	int time;
};

struct comp {
	bool operator()(SNAKE A, SNAKE B) {
		return A.time > B.time; // 시간이 작은 얘들 먼저 빠지도록
	}
};

struct comp2 {
	bool operator()(pic a, pic b) {
		return a.first > b.first;
	}
};

priority_queue<SNAKE, vector<SNAKE>, comp> pq;
priority_queue<pii, vector<pii>, comp2> check;
vector<vector<int>> board;
set<pii> s;
int n, apple, snake;

bool isSafe(int r, int c) {
	return r && c && r <= n && c <= n;
}

int solve(int r, int c, int dir, int tm) {
	if (s.count({ r, c })) return tm; // 몸과 닿았다면 End
	if (!isSafe(r, c)) return tm; // 벽과 닿았다면 End

	int nextDir = dir;

	if (board[r][c] == ground) { // 사과가 없으므로 꼬리를 줄인다.
		SNAKE cur = pq.top();
		s.erase(s.find({ cur.r, cur.c }));
		pq.pop();
	}
	else if (board[r][c] == 1) board[r][c] = ground;
	// 사과가 있으므로, 꼬리를 줄이지 않고 사과를 먹는다(없앤다).

	s.insert({ r, c }); // 현재 위치로 뱀을 늘린다.
	pq.push({ r, c, tm });

	if (!check.empty() && tm == check.top().first){
		char dr = check.top().second;
		if (dr == 'D') nextDir = (dir + 1) % 4;
		else if (dr == 'L') nextDir = ((4 + dir) - 1) % 4;
		check.pop();
	}

	if (nextDir == Up) return solve(r - 1, c, Up, tm + 1);
	else if (nextDir == Down) return solve(r + 1, c, Down, tm + 1);
	else if (nextDir == Left) return solve(r, c - 1, Left, tm + 1);
	else return solve(r, c + 1, Right, tm + 1);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;

	board.assign(n + 1, vector<int>(n + 1, ground));

	cin >> apple;
	int r, c;
	for (int i = 0; i < apple; i++) {
		cin >> r >> c;

		board[r][c] = 1; // 사과가 있는 위치를 1로 초기화
	}

	cin >> snake;

	int t; char dr;
	for (int i = 0; i < snake; i++) {
		cin >> t >> dr;

		check.push({ t, dr });
	}

	s.insert({ 1, 1 }); // 출발지점에 뱀을 둔다.
	pq.push({ 1, 1, 0 }); // 출발지점을 pq에 push 한다.

	cout << solve(1, 2, Right, 1);
}