[백준] 3190 뱀

백준 3190 뱀 문제 풀이입니다.

뱀

이 문제는 주어진 조건대로 뱀 길이를 늘리고 줄이고 하면 되는 문제였습니다. 따라서 dfs를 쓰든 bfs를 쓰든 상관은 없습니다.

전 그중 bfs를 사용하였고, 뱀의 길이는 deque로 표현하였습니다.

이후 방향 변환 정보는 vector를 사용해서 쭉 저장한 다음에 매 이동 횟수와 정보를 비교하여 일치한다면 방향 위치를 변환시켜주는 것으로 구현을 하였습니다.

소스코드는 다음과 같습니다.

Source Code:

```cpp
#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
using namespace std;

#define MAX 101
typedef pair<int, int> p;

int Map[MAX][MAX];

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

int N, K, L;

vector<pair<int,char>> Rotate_info;

deque<p> q;
bool visit[MAX][MAX] = { false, };

int main() {

	cin >> N >> K;

	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		Map[x][y] = 1;
	}

	cin >> L;

	for (int i = 0; i < L; i++) {
		int second;
		char dir;
		cin >> second >> dir;
		Rotate_info.push_back({ second,dir });
	}

	q.push_back({ 1,1 });

	int cur = 0;
	int result = 0;
	int dir = 1;

	while (!q.empty()) {
		result++;

		p tmp = q.back();

		int x = tmp.first;
		int y = tmp.second;

		int nx = x + dx[dir];
		int ny = y + dy[dir];

		if (visit[nx][ny] || nx < 1 || nx > N || ny < 1 || ny > N)break;

		visit[nx][ny] = true;
		q.push_back({ nx,ny });

		if (Map[nx][ny] == 1)
			Map[nx][ny] = 0;
		else {
			p ttmp = q.front();
			q.pop_front();
			visit[ttmp.first][ttmp.second] = false;
		}

		if (cur < L && result == Rotate_info[cur].first) {
			if (Rotate_info[cur++].second == 'D') {
				dir = (dir + 1 + 4) % 4;
			}
			else {
				dir = (dir - 1 + 4) % 4;
			}
		}
	}

	cout << result;

	return 0;
}

```

궁금하신 점은 댓글 남겨 주세요!!

Summary

• 되도록이면 푼 문제들 계속 올리도록 하겠습니다…
• 또 간혹 설명이 이해가 안간다면 말해주시면 그림까지 같이 넣는 노력을 하겠습니다. 감사합니다.